Saturating right congruences. (English) Zbl 0716.68057

Table-transition automata are considered, related to Muller automata, for recognizing rational \(\omega\)-languages. The deterministic automata are mainly investigated, because they are isomorphic to a family of finite right congruences satisfying a property of saturation similar to those defined for congruences by A. Arnold [Lect. Notes Computer Sci. 192, 18-27 (1985; Zbl 0612.68073)] and J. R. Büchi (Proc. Internat. Congress on Logic, Methodology and Philosophy, Stanford Univ. Press, 1962, 1-11). Finally, a variant of the property used by L. H. Landweber [Math. Syst. Theory 3, 376-384 (1969)] for characterizing deterministic \(\omega\)-languages is given.
Reviewer: G.Paun


68Q45 Formal languages and automata


Zbl 0612.68073
Full Text: DOI EuDML


[1] A. ARNOLD, Deterministic and non-anbiguous rational w-languages, L.N.C.S., 1984, n^\circ 192, pp. 18-27. Zbl0612.68073 MR814729 · Zbl 0612.68073
[2] J. R. BÜCHI, On a decision method in restricted second order arithmetic, Proc. Internat. Congress on Logic, Methodology and philosophy, Stanford Univ. Press, 1962, pp. 1-11. Zbl0147.25103 MR183636 · Zbl 0147.25103
[3] S. EILENBERG, Automata, Languages and Machines, Vol. A., Academic Press, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[4] L. H. LANDWEBER, Decision problems for w-automata, Math. Sys. Theor., 1969, 3, pp. 376-384. Zbl0182.02402 MR260595 · Zbl 0182.02402 · doi:10.1007/BF01691063
[5] B. LE SAEC, Thèse de doctorat. Étude de la reconnaissabilité des langages rationnels de mots infinis, 1986, n^\circ 85, Université de Bordeaux.
[6] R. MCNAUGHTON, Testing and generating infinité sequences by finite automaton. Information and control, 1966, n^\circ 9, pp. 521-530. Zbl0212.33902 MR213241 · Zbl 0212.33902 · doi:10.1016/S0019-9958(66)80013-X
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.