In this work, we provide a simple coalgebraic characterisation of regular ?-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 Ohm-automata. In earlier work we introduced Ohm-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 Ohm-automata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Ohm-automata are expressively complete for the regular ?-languages. We show that, due to their coalgebraic nature, Ohm-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 Ohm-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 ?-languages.
Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages
Ciancia V;
2019
Abstract
In this work, we provide a simple coalgebraic characterisation of regular ?-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 Ohm-automata. In earlier work we introduced Ohm-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 Ohm-automata by proposing them as a new kind of acceptor for arbitrary streams. We prove that Ohm-automata are expressively complete for the regular ?-languages. We show that, due to their coalgebraic nature, Ohm-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 Ohm-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 ?-languages.File | Dimensione | Formato | |
---|---|---|---|
prod_410609-doc_150863.pdf
accesso aperto
Descrizione: Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages
Tipologia:
Versione Editoriale (PDF)
Dimensione
512.72 kB
Formato
Adobe PDF
|
512.72 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.