Dual adjunction between Ω-automata and Wilke algebra quotients

Tools

Chernev, Anton and Hansen, Helle Hvid and Kupke, Clemens; Anutariya, Chutiporn and Bonsangue, Marcello M., eds. (2024) Dual adjunction between Ω-automata and Wilke algebra quotients. In: Theoretical Aspects of Computing – ICTAC 2024. Lecture Notes in Computer Science . Springer, THA, pp. 96-113. ISBN 9783031770197 (https://doi.org/10.1007/978-3-031-77019-7_6)

[thumbnail of Chernev-etal-Springer-2024-Dual-adjunction-between-Omega-automata-and-Wilke-algebra]
Preview
 Text. Filename: Chernev-etal-Springer-2024-Dual-adjunction-between-Omega-automata-and-Wilke-algebra.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (382kB)| Preview

Abstract

Ω-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.

ORCID iDs

Chernev, Anton, Hansen, Helle Hvid and Kupke, Clemens ORCID logoORCID: https://orcid.org/0000-0002-0502-391X; Anutariya, Chutiporn and Bonsangue, Marcello M.
CORE (COnnecting REpositories)