דנה פיסמן

A regular language is almost fully characterized by its right congruence relation. Indeed, a regular language can always be recognized by a DFA isomorphic to the automaton corresponding to its right congruence, henceforth the rightcon automaton. The same does not hold for regular ω-languages. The right congruence of a regular ω-language is not 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 the rightcon automaton. The class of weak regular ω-languages does have an informative right congruence. That is, any weak regular ω-language can always be recognized by a deterministic Büchi automaton that is isomorphic to the rightcon automaton. 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 an informative right congruence? Can we fully characterize the class of languages with a trivial right congruence? In this paper we try to place some additional pieces of this big puzzle.