×

Characterizations of rational \(\omega\)-languages by means of right congruences. (English) Zbl 0873.68115

Summary: By means of right congruences, we characterize in a unified way different classical classes of rational \(\omega\)-languages. A new congruence associated with an \(\omega\)-automaton is introduced named cycle congruence. The family of rational \(\omega\)-languages which have, by morphism, a unique minimal recognizing \(\omega\)-automaton is characterized. It appears that for such a minimal \(\omega\)-automaton, the cycle congruence coincides with the syntactic congruence of the recognized \(\omega\)-language. We prove that the other rational \(\omega\)-languages have an infinite number of minimal automaton.

MSC:

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnold, A., A syntactic congruence for rational ω-languages, Theoret. Comput. Sci., 39, 333-335 (1985) · Zbl 0578.68057
[2] Bücni, J. R., On a decision method in restricted second order arithmetic logic, (Proc. 1962 Internat. Congr. on Methodology and Philosophy of Sciences (1962), Stanford University Press: Stanford University Press Stanford, CA)
[3] Do Long Van; Le Saëc, B.; Litovski, I., A syntactic approach to deterministic ω-automata, (Krob, D., Théorie des Automates et Applications, Actes des Deuxièmes Journées (1991), Franco-Belges: Franco-Belges Rouen), 133-146
[4] Eilenberg, S., (Automata, Languages and Machines, Vol. 3A and B (1976), Academic Press: Academic Press New York)
[5] Landweber, L. H., Decisions problems for ω-automata, Math. Systems Theory, 3, 376-384 (1969) · Zbl 0182.02402
[6] Le Saëc, B., Saturating right congruences for rational ω-languages, RAIRO Inform. Théor. Appl., 24, 545-560 (1990) · Zbl 0716.68057
[7] Le Saëc, B.; Pin, J. E.; Weil, P., Finite semigroups with idempotent stabilizers and applications to automata theory, Internat. J. Algebra Comput., 1, 3, 291-314 (1991) · Zbl 0725.20043
[8] Maler, O.; Staiger, L., On syntactic congruences for ω-languages, (STACS’93. STACS’93, Lecture Notes in Computer Science, Vol. 665 (1993), Springer: Springer Berlin) · Zbl 0797.68093
[9] McNaughton, R., Testing and generating infinite sequences by finite automaton, Inform. and Control, 9, 521-530 (1966) · Zbl 0212.33902
[10] Müller, D., Infinite sequences and finite machines, (Proc. 4th IEEE Symp. on Switching Theory and Logical Design (1963)), 3-16
[11] Perrin, D., An introduction to finite automata on infinite words, (Lecture Notes in Computer Science, Vol. 192 (1984), Springer: Springer Berlin), 2-17
[12] Perrin, D.; Pin, J. E., Mots infinis, (LITP Report 93.40 (1993)), to appear · Zbl 0542.68068
[13] Safta, S., On the complexity of ω-automata, (29th Ann. Symp. on Foundation of Computer Sciences (1988)), 24-29
[14] Staiger, L., Finite-state ω-languages, J. Comput. System Sci., 27, 434-448 (1983) · Zbl 0541.68052
[15] Staiger, L.; Wagner, K., Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regularer Folgenmengen, Elektron. Informationscerab. Kybernetik EIK, 10, 7, 379-392 (1974) · Zbl 0301.94069
[16] Timermann, E., The three subfamilies of rational ω-languages closed under ω-transduction, Theoret. Comput. Sci., 76 (1990) · Zbl 0704.68069
[17] Trachenbrot, A., Finite automata and the logic of one-place predicates, Siberian Math. J., 3, 1, 103-131 (1962) · Zbl 0115.00701
[18] Wagner, K., On ω-regular sets, Inform. and Control, 43, 123-177 (1979) · Zbl 0434.68061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.