Аннотация:
The Kleene star is one of the most interesting algebraic operations which appear in
theoretical computer science. Being of inductive nature, the Kleene star makes propositional
substructural logics which involve it behave like stronger theories, like arithmetic.
We give a survey of results on algorithmic complexity results for theories which include
Kleene star. Most of the theories we shall discuss are (in)equational, since in richer
languages complexity becomes very high (Kozen, 2002). We compare classical results by
Kozen et al. on decidability of the equational theory of Kleene algebras with the new
undecidability results obtained by the author, for algebras with divisions (action
algebras). We shall also briefly discuss recent results, obtained in joint work with
S.O. Speranski, on systems with both the Kleene star and linear logic exponential
modality.
