2024/07/19 by Anton Chernev, Chernev, Anton, Helle Hvid Hansen +3
Computer Science · Mathematics · #Advanced Algebra and Logic #Commutative Algebra and Its Applications #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2407.14115
openalex publication_date 2024/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Ω-automata and Wilke algebras are formalisms for characterising ω-regular languages via their ultimately periodic words. Ω-automata read finite representations of ultimately periodic words, called lassos, and they are a subclass of lasso automata. We introduce lasso semigroups as a generalisation of Wilke algebras that mirrors how lasso automata generalise Ω-automata, and we show that finite lasso semigroups characterise regular lasso languages. We then show a dual adjunction between lasso automata and quotients of the free lasso semigroup with a recognising set, and as our main result we show that this dual adjunction restricts to one between Ω-automata and quotients of the free Wilke algebra with a recognising set.