
A Homomorphism Concept for omega-Regularity
Author(s) -
Nils Klarlund
Publication year - 1994
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v1i11.21659
Subject(s) - homomorphism , mathematics , rotation formalisms in three dimensions , discrete mathematics , representation (politics) , congruence relation , pure mathematics , combinatorics , geometry , politics , political science , law
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.