Maler, Oded; Staiger, Ludwig :
On syntactic congruences for $\omega$-languages.
( English
)
Enjalbert, Patrice (ed.) et al., STACS 93. 10th annual symposium on
theoretical aspects of computer science, Wuerzburg, Germany, February 25-
27, 1993. Proceedings. Berlin: Springer-Verlag, (ISBN 3-540-56503-5).
Lect. Notes Comput. Sci. 665, 586-594 (1993).
For $\omega$-languages several notions of syntactic congruence were defined. The present paper investigates 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 refinements investigated by A. Arnold [Theor. Comput. Sci. 39, 333-335 (1985; Zbl.578.68057)]. 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. As the main result we derive a condition which guarantees that the simple syntactic congruence and Arnold's syntactic congruence coincide and show that all $\omega$-languages in the Borel class $F_\sigma \cap G_\delta$ satisfy this condition.
Finally we define an alternative canonical object for $\omega$-languages,
namely a family of right-congruence relations. Using this object we give a
necessary and sufficient condition for a regular $\omega$-language to be
accepted by its minimal-state automaton.
Publ. Year: 1993
Document Type: CA
Maler, Oded; Staiger, Ludwig:
On syntactic congruences for $\omega$-languages and the minimization of
$\omega$-automata.( English)
Bull. EATCS 53, 447-448 (1994).
The paper appeared in the Problems and solutions section of the Bulletin of the EATCS. It points out that for the case of $\omega$-languages (sets of semi-infinite words) the relationships between accepting automata and recognizing (right) congruences are not as simply described as for the case of languages (sets of finite words).
In the case of languages $W \subseteq \Sigma^*$ the well-known Kleene- Myhill-Nerode Theorem states that $W$ is regular iff its right congruence $\sim_W$, or equivalently its syntactic congruence $\simeq_W$ are of finite index. Moreover these relations are the coarsest (right) congruences such that $W$ is representable as a union of congruence classes, and $\sim_W$ is isomorphic to the minimal deterministic automaton accepting $W \subseteq \Sigma^*$.
As just mentioned, in case of $\omega$-languages things are more
complicated. The paper hints to several of these problems, some of which
are still open, and gives references to (partial) solutions.
L. Staiger (Pulheim)
Publ. Year: 1994
Document Type: J