Abstract
In this work, we provide a simple coalgebraic characterisation of regular omegalanguages based on languages of lassos, and prove a number of related mathematical results, framed into the theory of a new kind of automata called Omegaautomata. In earlier work we introduced Omegaautomata as twosorted structures that naturally operate on lassos, pairs of words encoding ultimately periodic streams (infinite words). Here we extend the scope of these Omegaautomata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Omegaautomata are expressively complete for the regular omegalanguages. We show that, due to their coalgebraic nature, Omegaautomata 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 Omegaautomata that exactly captures language equivalence and allows for a simple minimization procedure. We also prove a coalgebraic MyhillNerode 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 omegalanguages.
BibTeX  Entry
@InProceedings{ciancia_et_al:LIPIcs:2019:11433,
author = {Vincenzo Ciancia and Yde Venema},
title = {{OmegaAutomata: A Coalgebraic Perspective on Regular omegaLanguages}},
booktitle = {8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
pages = {5:15:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771207},
ISSN = {18688969},
year = {2019},
volume = {139},
editor = {Markus Roggenbach and Ana Sokolova},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11433},
URN = {urn:nbn:de:0030drops114338},
doi = {10.4230/LIPIcs.CALCO.2019.5},
annote = {Keywords: omegaautomata, regular omegalanguages, coalgebra, streams, bisimilarity}
}
Keywords: 

omegaautomata, regular omegalanguages, coalgebra, streams, bisimilarity 
Collection: 

8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019) 
Issue Date: 

2019 
Date of publication: 

25.11.2019 