Dana Fisman

A regular language is almost fully characterized by its right congruence relation. The same does not hold for regular ω-languages. The right congruence of a regular ω-language may not be informative enough; many regular ω-languages have a trivial right congruence, and in general it is not always possible to define an ω-automaton recognizing a given language that is isomorphic to its right congruence. The weak regular ω-languages do have fully informative right congruences. That is, any weak regular ω-language can always be recognized by a deterministic Bu¨chi automaton that is isomorphic to its right congruence. Weak regular ω-languages reside in the lower levels of the expressiveness hierarchy of regular ω-languages. Are there more expressive sub-classes of regular ω-languages that have fully informative right congruences? Can we characterize the class of languages that have trivial right congruences? In this paper we try to place some additional pieces of this big puzzle.