×

The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction. (English) Zbl 0704.68069

Summary: We prove that there are exactly three subfamilies of rational \(\omega\)- languages which are closed under \(\omega\)-transduction: the family of rational adherences; the family of rational \(\omega\)-languages whose complementary is deterministic; and the whole family of rational \(\omega\)-languages.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beauquier, D.; Perrin, D., Codeterministic automata on infinite words, Inform. Process. Lett., 20, 95-98 (1985) · Zbl 0571.68073
[2] Boassun, L.; Nivat, M., Adherences of languages, J. Somput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[3] Büchi, J. R., On a decision method in restricted order arithmetic, (Proc. 1960 Internat. Congress for Logic (1960), Stanford University Press), 1-11 · Zbl 0147.25103
[4] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[5] Gire, F., Relations rationnelles infinitaires, Thèse de 3ème cycle (1981), Paris VII · Zbl 0552.68064
[6] Gire, F., Une extension aux mots infinis de la notion de transduction rationnelle, (6th GI Conf.. 6th GI Conf., Lecture Notes in Computer Science, 145 (1983), Springer: Springer Berlin), 123-139 · Zbl 0495.68063
[7] Gire, F.; Nivat, M., Relations rationnelles infinitaires, Calcolo, 21, 91-125 (1984) · Zbl 0552.68064
[8] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discrete Appl. Math., 5, 243-246 (1983) · Zbl 0499.68031
[9] Landweber, L. H., Decision problems for \(ω\)-automata, Math. Systems Theory, 3, 376-384 (1969) · Zbl 0182.02402
[10] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (Lecture Notes in Computer Science, 154 (1983), Springer: Springer Berlin), 420-432 · Zbl 0523.68067
[11] Latteux, M.; Timmerman, E., Two characterizations of rational adherences, Theoret. Comput. Sci., 46, 101-106 (1986) · Zbl 0618.68066
[12] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and Control, 9, 521-530 (1966) · Zbl 0212.33902
[13] Pin, J. E., Sur le monoïde syntactique de \(L^∗\) lorsque \(L\) est un langage fini, Theoret. Comput. Sci., 7, 211-215 (1978) · Zbl 0388.20050
[14] Staiger, L., Sequential mappings of \(ω\)-languages, RAIRO Inform. Théor. Appl., 21, 147-173 (1987) · Zbl 0634.68070
[15] Staiger, L., Research in the theory of \(ω\)-languages, J. Inform. Process. Cybernet. EIK, 23, 415-439 (1987) · Zbl 0637.68095
[16] Takahashi, M.; Yamasaki, H., A note on \(ω\)-regular languages, Theoret. Comput. Sci., 23, 217-225 (1983) · Zbl 0517.68072
[17] Tison, S., Mots infinis et processus. Objects infinitaires et topologie, Thèse de 3ème cycle, 1 (1983), Lille
[18] Turakainen, P., A homomorphic characterization of principal semi-AFLs without using intersection with regular sets, Inform. Sci., 27, 141-149 (1982) · Zbl 0506.68063
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.