On Kleene algebras (Q5894726)

This paper deals with Kleene relation algebras. In 1984, B. Jónsson posed the following problem: Is the equational theory of Kleene algebras (inversion-free Kleene algebras) finitely based? In this paper the authors give a negative answer for the case of inversion-free Kleene algebras. The proof is obtained by passing from the algebras of binary relations to the algebras of regular languages. The main idea is to use a result of Redko and Salomaa for regular languages, and a result of Kozen for the algebras of regular languages. In the paper it is also proved that the word problem for Kleene algebras (and some other varieties of algebras) is unsolvable.