matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университетmatatecs-20Research ArticleСТАТЬИО распознаваемости для семейств алгебраических структурOn learning for families of algebraic structuresБаженовН. А.BazhenovN. A.

Николай Алексеевич Баженов

пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090

Nikolay Alekseevich Bazhenov

4 Acad. Koptyug Avе., Novosibirsk 630090

bazhenov@math.nsc.ruИнститут математики им. С.Л. Соболева СО РАНРоссияSobolev Institute of MathematicsRussian Federation20230811202313321Copyright © Баженов Н.А., 20232023Баженов Н.А.Bazhenov N.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/20

Приводится обзор недавних результатов об алгоритмическом распознавании (algorithmic learning) для семейств счетных алгебраических структур. В рамках этого подхода распознающее устройство на каждом шаге процесса распознавания получает конечный объем информации о данной счетной структуре S (которую нужно распознать), а также выдает гипотезу, описывающую тип изоморфизма S. Если последовательность выдаваемых гипотез сходится к правильному ответу, то распознавание считается успешным. В работе обсуждаются результаты о связи распознаваемости с синтаксическими свойствами структур S. Также приводятся результаты о новом подходе к распознаваемости, основанном на отношениях эквивалентности на пространстве Кантора.

We survey the recent results on algorithmic learning for families of countable algebraic structures. Within this framework, at each step a learner obtains a finite amount of data about a given countable structure S (which is supposed to be learned), and then the learner outputs a conjecture describing the isomorphism type of S. If the sequence of conjectures converges to the correct answer, then the learning procedure is successful. The paper discusses the results connecting learnability with syntactic properties of structures S. We also give some results on the new approach to learnability which uses equivalence relations on the Cantor space.

теория алгоритмического распознаванияиндуктивный выводвычислимая структурабесконечные формулыборелевское отношение эквивалентностиalgorithmic learning theoryinductive inferencecomputable structureinfinitary formulasBorel equivalence relationРабота выполнена при поддержке Математического Центра в Академгородке, соглашение с Министерством науки и высшего образования Российской Федерации № 075-15-2022-281.The work is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.ReferencesH. Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30 (1), 49–57 (1965).H. Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30 (1), 49–57 (1965).E.M. Gold, Language identification in the limit, Inf. Control 10 (5), 447–474 (1967). DOI: https://doi.org/10.1016/S0019-9958(67)91165-5E.M. Gold, Language identification in the limit, Inf. Control 10 (5), 447–474 (1967). DOI: https://doi.org/10.1016/S0019-9958(67)91165-5S. Jain, D. Osherson, J.S. Royer, A. Sharma, Systems that learn: An introduction to learning theory, MIT Press, Cambridge, Massachusetts, 1999.S. Jain, D. Osherson, J.S. Royer, A. Sharma, Systems that learn: An introduction to learning theory, MIT Press, Cambridge, Massachusetts, 1999.S. Lange, T. Zeugmann, S. Zilles, Learning indexed families of recursive languages from positive data: A survey, Theor. Comput. Sci. 397 (1–3), 194–232 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.030S. Lange, T. Zeugmann, S. Zilles, Learning indexed families of recursive languages from positive data: A survey, Theor. Comput. Sci. 397 (1–3), 194–232 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.030T. Zeugmann, S. Zilles, Learning recursive functions: A survey, Theor. Comput. Sci. 397 (1–3), 4–56 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.021T. Zeugmann, S. Zilles, Learning recursive functions: A survey, Theor. Comput. Sci. 397 (1–3), 4–56 (2008). DOI: https://doi.org/10.1016/j.tcs.2008.02.021F. Stephan, Y. Ventsov, Learning algebraic structures from text, Theor. Comput. Sci. 268 (2), 221–273 (2001). DOI: https://doi.org/10.1016/S0304-3975(00)00272-3F. Stephan, Y. Ventsov, Learning algebraic structures from text, Theor. Comput. Sci. 268 (2), 221–273 (2001). DOI: https://doi.org/10.1016/S0304-3975(00)00272-3W. Merkle, F. Stephan, Trees and learning, J. Comput. Syst. Sci. 68 (1), 134–156 (2004). DOI: https://doi.org/10.1016/j.jcss.2003.08.001W. Merkle, F. Stephan, Trees and learning, J. Comput. Syst. Sci. 68 (1), 134–156 (2004). DOI: https://doi.org/10.1016/j.jcss.2003.08.001V. S. Harizanov, F. Stephan, On the learnability of vector spaces, J. Comput. Syst. Sci. 73 (1), 109–122 (2007). DOI: https://doi.org/10.1016/j.jcss.2006.09.001V. S. Harizanov, F. Stephan, On the learnability of vector spaces, J. Comput. Syst. Sci. 73 (1), 109–122 (2007). DOI: https://doi.org/10.1016/j.jcss.2006.09.001Z. Gao, F. Stephan, G. Wu, A. Yamamoto, Learning families of closed sets in matroids, in: M. J. Dinneen, B. Khoussainov, A. Nies (eds.), Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012 (Lect. Notes Comput. Sci. 7160), Springer, Berlin, 120–139 (2012). DOI: https://doi.org/10.1007/978-3-642-27654-5_10Z. Gao, F. Stephan, G. Wu, A. Yamamoto, Learning families of closed sets in matroids, in: M. J. Dinneen, B. Khoussainov, A. Nies (eds.), Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012 (Lect. Notes Comput. Sci. 7160), Springer, Berlin, 120–139 (2012). DOI: https://doi.org/10.1007/978-3-642-27654-5_10E. Fokina, T. K¨otzing, L. San Mauro, Limit learning equivalence structures, Proc. Mach. Learn. Res. (PMLR) 98, 383–403 (2019).E. Fokina, T. K¨otzing, L. San Mauro, Limit learning equivalence structures, Proc. Mach. Learn. Res. (PMLR) 98, 383–403 (2019).N. Bazhenov, E. Fokina, L. San Mauro, Learning families of algebraic structures from informant, Inf. Comput. 275, article id 104590 (2020). DOI: https://doi.org/10.1016/j.ic.2020.104590N. Bazhenov, E. Fokina, L. San Mauro, Learning families of algebraic structures from informant, Inf. Comput. 275, article id 104590 (2020). DOI: https://doi.org/10.1016/j.ic.2020.104590N. Bazhenov, L. San Mauro, On the Turing complexity of learning finite families of algebraic structures, J. Log. Comput. 31 (7), 1891–1900 (2021). DOI: https://doi.org/10.1093/logcom/exab044N. Bazhenov, L. San Mauro, On the Turing complexity of learning finite families of algebraic structures, J. Log. Comput. 31 (7), 1891–1900 (2021). DOI: https://doi.org/10.1093/logcom/exab044N. Bazhenov, V. Cipriani, L. San Mauro, Learning algebraic structures with the help of Borel equivalence relations, Theor. Comput. Sci. 951, article id 113762 (2023). DOI: https://doi.org/10.1016/j.tcs.2023.113762N. Bazhenov, V. Cipriani, L. San Mauro, Learning algebraic structures with the help of Borel equivalence relations, Theor. Comput. Sci. 951, article id 113762 (2023). DOI: https://doi.org/10.1016/j.tcs.2023.113762N. Bazhenov, V. Cipriani, L. San Mauro, Calculating the mind change complexity of learning algebraic structures, in: U. Berger, J.N.Y. Franklin, F. Manea, A. Pauly (eds.), Revolutions and Revelations in Computability, 18th Conference on Computability in Europe, CiE 2022 (Lect. Notes Comput. Sci. 13359), Springer, Cham, 1–12 (2022).N. Bazhenov, V. Cipriani, L. San Mauro, Calculating the mind change complexity of learning algebraic structures, in: U. Berger, J.N.Y. Franklin, F. Manea, A. Pauly (eds.), Revolutions and Revelations in Computability, 18th Conference on Computability in Europe, CiE 2022 (Lect. Notes Comput. Sci. 13359), Springer, Cham, 1–12 (2022).Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN: 3-540-15299-7С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научн. кн., Новосибирск, 1999.S.S. Goncharov, Yu.L. Ershov, Constructive Models, Springer, New York, 2000.C.J. Ash, J.F. Knight, Computable structures and the hyperarithmetical hierarchy (Stud. Logic Found. Math. 144), Elsevier Science B.V., Amsterdam, 2000.C.J. Ash, J.F. Knight, Computable structures and the hyperarithmetical hierarchy (Stud. Logic Found. Math. 144), Elsevier Science B.V., Amsterdam, 2000.S. Gao, Invariant descriptive set theory, CRC Press, Boca Raton, FL, 2009.S. Gao, Invariant descriptive set theory, CRC Press, Boca Raton, FL, 2009.C. Glymour, Inductive inference in the limit, Erkenntnis, 22, 23–31 (1985). DOI: https://doi.org/10.1007/978-94-017-1456-3_2C. Glymour, Inductive inference in the limit, Erkenntnis, 22, 23–31 (1985). DOI: https://doi.org/10.1007/978-94-017-1456-3_2E. Martin, D. Osherson, Elements of scientific inquiry, MIT Press, Cambridge, 1998.E. Martin, D. Osherson, Elements of scientific inquiry, MIT Press, Cambridge, 1998.V. Kanovei, Borel equivalence relations: Structure and classification, AMS, Providence R.I., 2008.V. Kanovei, Borel equivalence relations: Structure and classification, AMS, Providence R.I., 2008.G. Hjorth, Borel equivalence relations, in: M. Foreman, A. Kanamori (eds.), Handbook of set theory, Springer, Heidelberg, 297–332 (2010).G. Hjorth, Borel equivalence relations, in: M. Foreman, A. Kanamori (eds.), Handbook of set theory, Springer, Heidelberg, 297–332 (2010).L.A. Harrington, A.S. Kechris, A. Louveau, A Glimm–Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (4), 903–928 (1990). DOI: https://doi.org/10.2307/1990906L.A. Harrington, A.S. Kechris, A. Louveau, A Glimm–Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (4), 903–928 (1990). DOI: https://doi.org/10.2307/1990906У. Калверт, Д. Камминс, Д.Ф. Найт, С. Миллер, Сравнение классов конечных структур, Алгебра и логика 43 (6), 666–701 (2004). URL: https://www.mathnet.ru/rus/al103W. Calvert, D. Cummins, J.F. Knight, S. Miller, Comparing Classes of Finite Structures, Algebra and Logic 43 (6), 374–392 (2004). DOI: https://doi.org/10.1023/B:ALLO.0000048827.30718.2cJ.F. Knight, S. Miller, M. Vanden Boom, Turing computable embeddings, J. Symb. Log. 72 (3), 901–918 (2007).J.F. Knight, S. Miller, M. Vanden Boom, Turing computable embeddings, J. Symb. Log. 72 (3), 901–918 (2007).S. Coskey, J.D. Hamkins, R. Miller, The hierarchy of equivalence relations on the natural numbers under computable reducibility, Computability, 1 (1), 15–38 (2012). DOI: https://doi.org/10.3233/COM-2012-004S. Coskey, J.D. Hamkins, R. Miller, The hierarchy of equivalence relations on the natural numbers under computable reducibility, Computability, 1 (1), 15–38 (2012). DOI: https://doi.org/10.3233/COM-2012-004

The authors declare that there are no conflicts of interest present.