EUVIMEDEUVIMED entdecken
Crossref

Algorithmic complexity of theories with Kleene iteration

Stepan Lvovich Kuznetsov

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →