Omega-Automata: A Coalgebraic Perspective on Regular omega-Languages

Ciancia V, Venema Y

Coalgebra  Automata  Infinite words  Computer Science  Modal logic  Omega automata  Streams  general works  000 Computer science  knowledge 

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.

Source: LEIBNIZ INTERNATIONAL PROCEEDINGS IN INFORMATICS, pp. 5:1-5:18

Metrics