Dual Adjunction Between \(\varOmega \) -Automata and Wilke Algebra Quotients
摘要
\(\varOmega \) -automata and Wilke algebras are formalisms for characterising \(\omega \) -regular languages via their ultimately periodic words. \(\varOmega \) -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 \(\varOmega \) -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 \(\varOmega \) -automata and quotients of the free Wilke algebra with a recognising set.