?
Алгоритмическая сложность теорий с итерацией Клини
Итерация (звёздочка) Клини – это одна из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. Исследования структур с этой операцией – алгебр Клини и их расширений – начинаются с классического понятия регулярных выражений, задающих формальные языки. Впоследствии были введены так называемые алгебры действий (В. Пратт, 1991 г.; Д. Козен, 1994 г.), или алгебры Клини с делениями. В этих структурах звёздочка Клини сочетается с делениями, согласованными с частичным порядком (такие операции были введены ранее в работе В. Крулля, 1924 г.). В настоящей статье дан обзор результатов об алгоритмической сложности для логических теорий структур с итерацией Клини. Несмотря на то что простейшая из таких теорий, теория равенства регулярных выражений, алгоритмически разрешима, её обобщения, такие как хорновы теории и их фрагменты, а также теории с делениями, практически сразу становятся неразрешимыми. Особенно интересен здесь случай ∗-непрерывных алгебр Клини, где итерация задаётся как предел степеней элемента (в общем случае итерация определяется как неподвижная точка). На логическом языке ∗-непрерывность соответствует ω-правилу, и сложность таких теорий может достигать уровня Π11-полноты.