Two characterizations of rational adherences. (English) Zbl 0618.68066

We present two characterizations of rational adherences in terms of finite sets, strictly alphabetic morphisms and inverse uniform morphisms. We deduce a similar characterization for rational \(\omega\)-languages.


68Q45 Formal languages and automata
Full Text: DOI


[1] Boasson, L.; Nivat, M., Adherences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[2] Culik, K.; Fich, F. E.; Salomaa, A., A homomorphic characterization of regular languages, Discrete Appl. Math., 4, 149-152 (1982) · Zbl 0481.68069
[3] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[4] Gire, F., Relations rationnelles infinitaires, (Thèse de 3ème cycle (1981), Univ. de Paris VII) · Zbl 0552.68064
[5] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discrete Appl. Math., 5, 243-246 (1983) · Zbl 0499.68031
[6] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, Lecture Notes Computer Sciences, 154, 420-432 (1983) · Zbl 0523.68067
[7] MacNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and Control., 9, 521-530 (1966) · Zbl 0212.33902
[8] Nivat, M., Sur les ensembles de mots infinis engendrés par une grammaire algébrique, RAIRO Inform. Théor., 12, 259-278 (1978) · Zbl 0387.68050
[9] Pin, J. E., Sur le monoïde syntactique de \(L^∗ lorsque L\) est un language fini, Theoret. Comput. Sci., 7, 211-215 (1978) · Zbl 0388.20050
[10] Tison, S., Mots infinis et processus: Objets infinitaires et topologie, (Thèse de 3ième cycle (1983), Université de Lille 1)
[11] 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.