TY - UNPB
T1 - Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients
AU - Chernev, Anton
AU - Hansen, Helle Hvid
AU - Kupke, Clemens
PY - 2024/7/19
Y1 - 2024/7/19
N2 - $\Omega$-automata and Wilke algebras are formalisms for characterising $\omega$-regular languages via their ultimately periodic words. $\Omega$-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 $\Omega$-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 $\Omega$-automata and quotients of the free Wilke algebra with a recognising set.
AB - $\Omega$-automata and Wilke algebras are formalisms for characterising $\omega$-regular languages via their ultimately periodic words. $\Omega$-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 $\Omega$-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 $\Omega$-automata and quotients of the free Wilke algebra with a recognising set.
KW - cs.FL
U2 - 10.48550/arXiv.2407.14115
DO - 10.48550/arXiv.2407.14115
M3 - Preprint
BT - Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients
PB - arXiv
ER -