Kleene Theorems for Lasso Languages and ω-Languages

Automata operating on representations of ultimately periodic words were introduced as an alternative way of capturing acceptance of regular ω ω -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 ω ω -expressions, which yields a Kleene theorem for ω ω -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 ω ω -expressions.