Algorithmic complexity of theories with Kleene iteration
Russian Mathematical Surveys · 2026 · 81 (1) · 125-188
DOI: 10.4213/rm10268e ↗Kurz gefasst
Fachartikel in der Zeitschrift Russian Mathematical Surveys, online erschienen am 04.05.2026. Verfasst von Stepan Lvovich Kuznetsov. Die Arbeit nennt 83 Literaturangaben. Gefördert von: HSE Basic Research Program, Ministry of Science and Higher Education of the Russian Federation.
Abstract (Originalsprache)
Kleene iteration (star operator) is one of the most interesting algebraic operations arising in computer science. The studies of structures with this operation, Kleene algebras and their extensions, begin with the classical notion of regular expression describing formal languages. Subsequently, so-called action algebras (Pratt 1991, Kozen 1994), or Kleene algebras with division, were introduced. In these structures the Kleene star operator is combined with divisions compatible with a partial order (such operations had previously been introduced by Krull in 1924). This article gives a survey of results on algorithmic complexity for the logical theories of structures with Kleene iteration. Although the simplest of these theories, the theory of equality of regular expressions, is algorithmically decidable, some of its generalizations, such as Horn theories and fragments of these, as well as theories with division, almost immediately become undecidable. Particularly interesting is the case of $*$-continuous Kleene algebras, where iteration is defined as the limit of powers of an element (in the general case iteration is defined as a fixed point). In the language of logic, $*$-continuity corresponds to the omega rule, and the complexity of such theories can attain the level of $\Pi^1_1$-completeness. Bibliography: 83 titles.
Förderung
- HSE Basic Research Program
- Ministry of Science and Higher Education of the Russian Federation
Zitieren
APA
Kuznetsov, S. L. (2026). Algorithmic complexity of theories with Kleene iteration. Russian Mathematical Surveys, 81(1), 125-188. https://doi.org/10.4213/rm10268e
Vancouver
Kuznetsov SL. Algorithmic complexity of theories with Kleene iteration. Russian Mathematical Surveys. 2026;81(1):125-188. doi:10.4213/rm10268e
BibTeX
@article{Kuznetsov2026,
author = {Kuznetsov, Stepan Lvovich},
title = {Algorithmic complexity of theories with Kleene iteration},
journal = {Russian Mathematical Surveys},
year = {2026},
volume = {81},
number = {1},
pages = {125--188},
doi = {10.4213/rm10268e}
}
EUVIMED