Kleene Theorems for Lasso Languages and  \(\omega \) -Languages

Automata operating on pairs of words were introduced as an alternative way of capturing acceptance of regular \(\omega \) -languages. Families of DFAs and lasso automata operating on such pairs were defined subsequently, giving rise to minimisation algorithms, a Myhill-Nerode theorem and language learning algorithms. Yet Kleene theorems for these well-studied classes are still missing. We introduce rational lasso languages and expressions, show a Kleene theorem for lasso languages and explore the connection between rational lasso and \(\omega \) -expressions, which yields a Kleene theorem for \(\omega \) -languages and saturated lasso automata. For one direction of the Kleene theorems, we also provide a Brzozowski construction for lasso automata from rational lasso expressions.