2026-07-25T10:02:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11433 2024-03-06T10:47:06Z ddc:004 open_access

Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages Ciancia, Vincenzo Venema, Yde omega-automata regular omega-languages coalgebra streams bisimilarity In this work, we provide a simple coalgebraic characterisation of regular omega-languages based on languages of lassos, and prove a number of related mathematical results, framed into the theory of a new kind of automata called Omega-automata. In earlier work we introduced Omega-automata as two-sorted structures that naturally operate on lassos, pairs of words encoding ultimately periodic streams (infinite words). Here we extend the scope of these Omega-automata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Omega-automata are expressively complete for the regular omega-languages. We show that, due to their coalgebraic nature, Omega-automata share some attractive properties with deterministic automata operating on finite words, properties that other types of stream automata lack. In particular, we provide a simple, coalgebraic definition of bisimilarity between Omega-automata that exactly captures language equivalence and allows for a simple minimization procedure. We also prove a coalgebraic Myhill-Nerode style theorem for lasso languages, and use this result, in combination with a closure property on stream languages called lasso determinacy, to give a characterization of regular omega-languages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincenzo Ciancia and Yde Venema 2019 Is Part Of LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2019.5 urn:nbn:de:0030-drops-114338 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode