Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

Anton Chernev; Helle Hvid Hansen; Clemens Kupke

doi:10.1007/978-3-031-77019-7_6

Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

Anton Chernev^*, Helle Hvid Hansen, Clemens Kupke

^*Corresponding author for this work

Fundamental Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Downloads (Pure)

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 language	English
Title of host publication	Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings
Editors	Chutiporn Anutariya, Marcello M. Bonsangue
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	96-113
Number of pages	18
ISBN (Print)	9783031770180
DOIs	https://doi.org/10.1007/978-3-031-77019-7_6
Publication status	Published - 22-Nov-2024
Event	21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024 - Bangkok, Thailand Duration: 25-Nov-2024 → 29-Nov-2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15373 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024
Country/Territory	Thailand
City	Bangkok
Period	25/11/2024 → 29/11/2024

Keywords

Coalgebra
Infinite words
Ultimately periodic words
Wilke algebra
Ω-automata
ω-regular languages

Access to Document

10.1007/978-3-031-77019-7_6

Dual Adjunction Between Ω-Automata and Wilke Algebra QuotientsFinal publisher's version, 450 KBLicence: Taverne

Handle.net

Persistent link

Cite this

Chernev, A., Hansen, H. H., & Kupke, C. (2024). Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients. In C. Anutariya, & M. M. Bonsangue (Eds.), Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings (pp. 96-113). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15373 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-77019-7_6

Chernev, Anton ; Hansen, Helle Hvid ; Kupke, Clemens. / Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients. Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings. editor / Chutiporn Anutariya ; Marcello M. Bonsangue. Springer Science and Business Media Deutschland GmbH, 2024. pp. 96-113 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d3671e574ece45df9939413bd576166f,

title = "Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients",

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.",

keywords = "Coalgebra, Infinite words, Ultimately periodic words, Wilke algebra, Ω-automata, ω-regular languages",

author = "Anton Chernev and Hansen, {Helle Hvid} and Clemens Kupke",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024 ; Conference date: 25-11-2024 Through 29-11-2024",

year = "2024",

month = nov,

day = "22",

doi = "10.1007/978-3-031-77019-7_6",

language = "English",

isbn = "9783031770180",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "96--113",

editor = "Chutiporn Anutariya and Bonsangue, {Marcello M.}",

booktitle = "Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings",

}

Chernev, A , Hansen, HH & Kupke, C 2024, Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients. in C Anutariya & MM Bonsangue (eds), Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15373 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 96-113, 21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024, Bangkok, Thailand, 25/11/2024. https://doi.org/10.1007/978-3-031-77019-7_6

Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients. / Chernev, Anton ; Hansen, Helle Hvid; Kupke, Clemens.
Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings. ed. / Chutiporn Anutariya; Marcello M. Bonsangue. Springer Science and Business Media Deutschland GmbH, 2024. p. 96-113 (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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

AU - Chernev, Anton

AU - Hansen, Helle Hvid

AU - Kupke, Clemens

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2024/11/22

Y1 - 2024/11/22

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

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

KW - Coalgebra

KW - Infinite words

KW - Ultimately periodic words

KW - Wilke algebra

KW - Ω-automata

KW - ω-regular languages

UR - http://www.scopus.com/inward/record.url?scp=85210818593&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-77019-7_6

DO - 10.1007/978-3-031-77019-7_6

M3 - Conference contribution

AN - SCOPUS:85210818593

SN - 9783031770180

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 96

EP - 113

BT - Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings

A2 - Anutariya, Chutiporn

A2 - Bonsangue, Marcello M.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 21st International Colloquium on Theoretical Aspects of Computing, ICTAC 2024

Y2 - 25 November 2024 through 29 November 2024

ER -

Chernev A , Hansen HH, Kupke C. Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients. In Anutariya C, Bonsangue MM, editors, Theoretical Aspects of Computing – ICTAC 2024 - 21st International Colloquium, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 96-113. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-77019-7_6

Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

Abstract

Publication series

Conference

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Dual Adjunction Between Ω-Automata and Wilke Algebra Quotients

Cite this