| Autor: |
Chernev, Anton, Hansen, Helle Hvid, Kupke, Clemens |
| Rok vydání: |
2024 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
$\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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
