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.