Complexity of Theories for Structures with Kleene Star

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.