Алгоритмическая сложность теорий с итерацией Клини

Итерация (звёздочка) Клини – это одна из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. Исследования структур с этой операцией – алгебр Клини и их расширений – начинаются с классического понятия регулярных выражений, задающих формальные языки. Впоследствии были введены так называемые алгебры действий (В. Пратт, 1991 г.; Д. Козен, 1994 г.), или алгебры Клини с делениями. В этих структурах звёздочка Клини сочетается с делениями, согласованными с частичным порядком (такие операции были введены ранее в работе В. Крулля, 1924 г.). В настоящей статье дан обзор результатов об алгоритмической сложности для логических теорий структур с итерацией Клини. Несмотря на то что простейшая из таких теорий, теория равенства регулярных выражений, алгоритмически разрешима, её обобщения, такие как хорновы теории и их фрагменты, а также теории с делениями, практически сразу становятся неразрешимыми. Особенно интересен здесь случай $*$-непрерывных алгебр Клини, где итерация задаётся как предел степеней элемента (в общем случае итерация определяется как неподвижная точка). На логическом языке $*$-непрерывность соответствует $\omega$-правилу, и сложность таких теорий может достигать уровня $\Pi^1_1$-полноты.
Библиография: 83 названия.