Алгоритмическая сложность теорий с итерацией Клини | Кузнецов С. Л.

IV Конференция математических центров России Степан Кузнецов, МИАН Итерация (звёздочка) Клини — это одна из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. Исследования структур с этой операцией — алгебр Клини и их расширений — начинаются с классического понятия регулярных выражений, задающих формальные языки. Впоследствии были введены так называемые алгебры действий (Пратт 1991, Козен 1994), или алгебры Клини с делениями. В этих структурах звёздочка Клини сочетается с делениями, согласованными с частичным порядком (такие операции были введены ранее в работе Крулля, 1924). Доклад посвящён вопросам алгоритмической сложности логических теорий структур со звёздочкой Клини. Несмотря на то, что простейшая из таких теорий, теория равенства регулярных выражений, алгоритмически разрешима, её обобщения, такие как хорновы теории и их фрагменты, а также теории с делениями, практически сразу становятся неразрешимыми. Особенно интересен здесь случай ∗-непрерывных алгебр Клини, где итерация задаётся как предел степеней элемента (в общем случае итерация определяется как неподвижная точка). На логическом языке ∗-непрерывность соответствует ω-правилу, и сложность таких теорий может достигать уровня Π^1_1 -полноты. В докладе будет дан обзор результатов об алгоритмической сложности теорий — эквациональных, хорновых, первопорядковых — для алгебр Клини и алгебр действий, в общем и ∗-непрерывном случаях. Будет рассказано как о давно известных, так и о новых результатах в этой области, в том числе полученных докладчиком. [1] W. Buszkowski, E. Palka, Infinitary action logic: complexity, models and grammars, Studia Logica, 89 (2008), 1–18. [2] S. C. Kleene, Representation of events in nerve nets and finite automata, in: Automata Studies, Princeton Univ. Press, 1956, pp. 3–41. [3] D. Kozen, On action algebras, in: Logic and Information Flow, MIT Press, 1994, pp. 78– 88. [4] D. Kozen, On the complexity of reasoning in Kleene algebra, Inform. Comput., 179 (2002), 152–162. [5] S. Kuznetsov, Action logic is undeciable, ACM Trans. Comput. Logic, 22:2 (2021), art. 10. [6] S. L. Kuznetsov, S. O. Speranski, Infinitary action logic with exponentiation, Ann. Pure Appl. Logic, 173:2 (2022), art. 103057. [7] С. Л. Кузнецов, Алгоритмическая сложность теорий коммутативных алгебр Клини, Изв. РАН. Сер. матем., 88:2 (2024), 44–79. Слайды и аннотации:
точка me/mc4_conf_library
6-11 августа 2024 Санкт-Петербург