A Homomorphism Concept for omega-Regularity

Nils Klarlund

Abstract


The Myhill-Nerode Theorem (that for any regular language, there is a canonical recognizing device) is of paramount importance for the computational handling of many formalisms about finite words.

For infinite words, no prior concept of homomorphism or structural comparison seems to have generalized the Myhill-Nerode Theorem in the sense that the concept is both language preserving and representable by automata.

In this paper, we propose such a concept based on Families of Right Congruences (Maler and Staiger 93), which we view as a recognizing structures.

We also establish an exponential lower and upper bound on the change in size when a representation is reduced to its canonical form.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v1i11.21659
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library