Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

Research output: Working paperPreprintAcademic

18 Downloads (Pure)

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.
Original languageEnglish
PublisherarXiv
Number of pages27
DOIs
Publication statusSubmitted - 19-Jul-2024

Keywords

  • cs.FL

Fingerprint

Dive into the research topics of 'Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients'. Together they form a unique fingerprint.
  • Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

    Chernev, A., Hansen, H. H. & Kupke, C., 22-Nov-2024, Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings. Anutariya, C. & Bonsangue, M. M. (eds.). Springer Science and Business Media Deutschland GmbH, p. 96-113 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 15373 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Open Access
    File
    28 Downloads (Pure)

Cite this