Mike Cruchten

dblp:371/0963 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
0009-0002-5807-569XORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Kleene Theorems for Lasso Languages and ømega-Languages
abstract
Abstract Automata operating on representations of ultimately periodic words were introduced as an alternative way of capturing acceptance of regular $$\omega $$ ω -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 $$ ω -expressions, which yields a Kleene theorem for $$\omega $$ ω -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 $$ ω -expressions.
Mike Cruchten
Theory Comput. Syst.1
2024 Kleene Theorems for Lasso Languages and ømega-Languages
Mike Cruchten
TAMC1