О распознаваемости для семейств алгебраических структур
Аннотация
Приводится обзор недавних результатов об алгоритмическом распознавании (algorithmic learning) для семейств счетных алгебраических структур. В рамках этого подхода распознающее устройство на каждом шаге процесса распознавания получает конечный объем информации о данной счетной структуре S (которую нужно распознать), а также выдает гипотезу, описывающую тип изоморфизма S. Если последовательность выдаваемых гипотез сходится к правильному ответу, то распознавание считается успешным. В работе обсуждаются результаты о связи распознаваемости с синтаксическими свойствами структур S. Также приводятся результаты о новом подходе к распознаваемости, основанном на отношениях эквивалентности на пространстве Кантора.
Ключевые слова
теория алгоритмического распознавания,
индуктивный вывод,
вычислимая структура,
бесконечные формулы,
борелевское отношение эквивалентности
При поддержке: Работа выполнена при поддержке Математического Центра в Академгородке, соглашение с Министерством науки и высшего образования Российской Федерации № 075-15-2022-281.
Об авторе
Н. А. Баженов
Институт математики им. С.Л. Соболева СО РАН
Россия
Россия
Николай Алексеевич Баженов
пр. Акад. Коптюга, д. 4, г. Новосибирск, 630090
Список литературы
1. H. Putnam, Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30 (1), 49–57 (1965).
2. 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-5
3. S. Jain, D. Osherson, J.S. Royer, A. Sharma, Systems that learn: An introduction to learning theory, MIT Press, Cambridge, Massachusetts, 1999.
4. 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.030
5. T. 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.021
6. F. 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-3
7. W. 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.001
8. V. 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.001
9. Z. 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_10
10. E. Fokina, T. K¨otzing, L. San Mauro, Limit learning equivalence structures, Proc. Mach. Learn. Res. (PMLR) 98, 383–403 (2019).
11. 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.104590
12. N. 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/exab044
13. N. 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.113762
14. 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).
15. Р.И. Соар, Вычислимо перечислимые множества и степени, Казан. матем. о-во, Казань, 2000.
16. С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научн. кн., Новосибирск, 1999.
17. C.J. Ash, J.F. Knight, Computable structures and the hyperarithmetical hierarchy (Stud. Logic Found. Math. 144), Elsevier Science B.V., Amsterdam, 2000.
18. S. Gao, Invariant descriptive set theory, CRC Press, Boca Raton, FL, 2009.
19. C. Glymour, Inductive inference in the limit, Erkenntnis, 22, 23–31 (1985). DOI: https://doi.org/10.1007/978-94-017-1456-3_2
20. E. Martin, D. Osherson, Elements of scientific inquiry, MIT Press, Cambridge, 1998.
21. V. Kanovei, Borel equivalence relations: Structure and classification, AMS, Providence R.I., 2008.
22. G. Hjorth, Borel equivalence relations, in: M. Foreman, A. Kanamori (eds.), Handbook of set theory, Springer, Heidelberg, 297–332 (2010).
23. 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/1990906
24. У. Калверт, Д. Камминс, Д.Ф. Найт, С. Миллер, Сравнение классов конечных структур, Алгебра и логика 43 (6), 666–701 (2004). URL: https://www.mathnet.ru/rus/al103
25. J.F. Knight, S. Miller, M. Vanden Boom, Turing computable embeddings, J. Symb. Log. 72 (3), 901–918 (2007).
26. 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-004
Рецензия
Для цитирования:
Баженов Н.А. О распознаваемости для семейств алгебраических структур. Математика и теоретические компьютерные науки. 2023;1(3):3-21.
For citation:
Bazhenov N.A. On learning for families of algebraic structures. Mathematics and Theoretical Computer Science. 2023;1(3):3-21. (In Russ.)
Просмотров:
209
Послать статью по эл. почте 