Back to Search Start Over

Dual Adjunction Between $\Omega$-Automata and Wilke Algebra Quotients

Authors :
Chernev, Anton
Hansen, Helle Hvid
Kupke, Clemens
Publication Year :
2024

Abstract

$\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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2407.14115
Document Type :
Working Paper