Dual adjunction between Ω-automata and Wilke algebra quotients

Anton Chernev*, Helle Hvid Hansen, Clemens Kupke

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

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.

Original languageEnglish
Title of host publicationTheoretical Aspects of Computing – ICTAC 2024
Subtitle of host publication21st International Colloquium, Proceedings
EditorsChutiporn Anutariya, Marcello M. Bonsangue
Place of PublicationCham, Switzerland
PublisherSpringer
Pages96-113
Number of pages18
ISBN (Electronic)9783031770197
ISBN (Print)9783031770180
DOIs
Publication statusPublished - 22 Nov 2024
Event21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024 - Bangkok, Thailand
Duration: 25 Nov 202429 Nov 2024

Publication series

NameLecture Notes in Computer Science
Volume15373
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024
Country/TerritoryThailand
CityBangkok
Period25/11/2429/11/24

Keywords

  • coalgebra
  • infinite words
  • ultimately periodic words
  • Wilke algebra
  • Ω-automata
  • ω-regular languages

Fingerprint

Dive into the research topics of 'Dual adjunction between Ω-automata and Wilke algebra quotients'. Together they form a unique fingerprint.

Cite this