zbMATH — the first resource for mathematics

A morphic representation of EOL languages and other ETOL languages. (English) Zbl 0579.68046
Summary: The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L\(\cap R)\) where h is a morphism, R is a regular language and L is the maximal solution of an equation \(f(X)=g(X)\), where f is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.

68Q45 Formal languages and automata
Full Text: DOI
[1] Ehrenfeueht, A.; Rozenberg, G.; Ruohonen, K., A morphic representation of complements of recursively enumerable sets, J. ACM, 28, 706-714, (1981) · Zbl 0491.68078
[2] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., Structurally restricted maximal solutions of language equations involving morphisms, () · Zbl 0491.68078
[3] Ginsburg, S.; Rozenberg, G., TOL schemes and control sets, Information and control, 27, 109-125, (1975) · Zbl 0294.68027
[4] Herman, G.T.; Rozenberg, G., Developmental systems and languages, (1975), North-Holland Amsterdam · Zbl 0313.68068
[5] Karhumäki, J., On length sets of informationless L systems, (), 227-242
[6] Ruohonen, K., A note on language equations involving morphisms, Inform. process. lett., 7, 209-212, (1978) · Zbl 0385.68058
[7] Ruohonen, K., On machine characterization of nonrecursive hierarchies, Ann. univ. turkuensis, ser. A. I, 186, 87-101, (1984) · Zbl 0562.03023
[8] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.