VLDB 2026 Research / reviewers in the wild / expert
Mike Cruchten
dblp:371/0963
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | Kleene Theorems for Lasso Languages and ømega-LanguagesabstractAbstract 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 |
TAMC | 1 |