TY - GEN
T1 - Dual adjunction between Ω-automata and Wilke algebra quotients
AU - Chernev, Anton
AU - Hansen, Helle Hvid
AU - Kupke, Clemens
PY - 2024/11/22
Y1 - 2024/11/22
N2 - Ω-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.
AB - Ω-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.
KW - coalgebra
KW - infinite words
KW - ultimately periodic words
KW - Wilke algebra
KW - Ω-automata
KW - ω-regular languages
UR - http://www.scopus.com/inward/record.url?scp=85210818593&partnerID=8YFLogxK
UR - https://arxiv.org/abs/2407.14115
U2 - 10.1007/978-3-031-77019-7_6
DO - 10.1007/978-3-031-77019-7_6
M3 - Conference contribution book
AN - SCOPUS:85210818593
SN - 9783031770180
T3 - Lecture Notes in Computer Science
SP - 96
EP - 113
BT - Theoretical Aspects of Computing – ICTAC 2024
A2 - Anutariya, Chutiporn
A2 - Bonsangue, Marcello M.
PB - Springer
CY - Cham, Switzerland
T2 - 21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024
Y2 - 25 November 2024 through 29 November 2024
ER -