On Syntactic Congruences for omega-languages
O. Maler, L. Staiger
In this paper we investigate several questions related to
syntactic congruences and to minimal automata associated
with $\omega$- languages. In particular we investigate
relationships between the so-called simple (because it is a
simple translation from the usual definition in the case of
finitary languages) syntactic congruence and its infinitary
refinement investigated by Arnold. We show that in both
cases not every $\omega$-language having a finite syntactic
monoid is regular and we give a characterization of those
$\omega$-languages having finite syntactic monoids.
Among the main results we derive a condition which guarantees
that the simple syntactic congruence and Arnold's syntactic
congruence coincide and show that {\it all} (including
infinite-state) $\omega$- languages in the Borel class
$F_\s\cap G_\d$ satisfy this condition. We also show that
all $\omega$-languages in this class are accepted by their
minimal-state automaton --- provided they are accepted by
any Muller automaton.
Finally we develop an alternative thoery of recognizability of
$\omega$-languages by families of right-congruence relations,
and define a cannonical object (much smaller then Arnold's
monoid) associated with every $\omega$-language. Using this
notion of recognizability we give a {\it necessary and
sufficient} condition for a regular $\omega$-language to be
accepted by its minimal-state automaton.