Kleene Theorems for Lasso Languages and $$\omega $$-Languages

Abstract Automata operating on representations of ultimately periodic words were introduced as an alternative way of capturing acceptance of regular $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -languages. Families of DFAs and lasso automata (which use pairs of words to represent ultimately periodic words) followed, and gave rise to minimisation algorithms, a Myhill-Nerode theorem and language learning algorithms. Yet Kleene theorems for such a well-established class are still missing, and lasso languages have not been studied algebraically. We are filling this gap by introducing rational lasso languages, expressions and a theory of lasso languages. We show a Kleene theorem for lasso languages and explore the connection between rational lasso and $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -expressions, which yields a Kleene theorem for $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -languages with respect to saturated lasso automata. For one direction of the Kleene theorems, we also provide a Brzozowski construction for lasso automata from rational lasso expressions. Our results offer a method to construct saturated lasso automata from rational $$\omega $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -expressions.