×

zbMATH — the first resource for mathematics

On generalized DT0L systems and their fixed points. (English) Zbl 0824.68059
Summary: We study a generalization of DT0L systems obtained by considering noncommutative polynomials together with mappings attaching a morphism to each variable. We call the least fixed points of such pairs generalized DT0L languages and study their basic properties.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ehrenfeucht, A.; Lee, K.P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. comput. sci., 1, 59-75, (1975) · Zbl 0316.68043
[2] Ehrenfeucht, A.; Lee, K.P.; Rozenberg, G., On the number of subwords of everywhere growing DT0L languages, Discrete math., 15, 223-234, (1976) · Zbl 0332.68053
[3] Ehrenfeucht, A.; Rozenberg, G., A limit theorem for sets of subwords in deterministic T0L systems, Inform. process. lett., 2, 70-73, (1973) · Zbl 0299.68044
[4] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., A morphic representation of complements of recursively enumerable sets, J. ACM, 28, 706-714, (1981) · Zbl 0491.68078
[5] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., Structurally restricted maximal solutions of language equations involving morphisms, () · Zbl 0491.68078
[6] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., A morphic representation of E0L languages and other ET0L languages, Discrete appl. math., 12, 115-122, (1985) · Zbl 0579.68046
[7] Herman, G.T.; Rozenberg, G., Developmental systems and languages, (1975), North-Holland Amsterdam · Zbl 0313.68068
[8] Honkala, J., Regularity properties of L ambiguities of morphisms, () · Zbl 0766.68079
[9] Honkala, J., On D0L systems with immigration, Theoret. comput. sci., 120, 2, 229-245, (1993) · Zbl 0801.68104
[10] Honkala, J.; Salomaa, A., L morphisms: bounded delay and regularity of ambiguity, (), 566-574 · Zbl 0766.68078
[11] Maurer, H.; Salomaa, A.; Wood, D., L codes and number systems, Theoret. comput. sci., 22, 331-346, (1983) · Zbl 0531.68027
[12] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[13] Rozenberg, G.; Salomaa, A., The book of L, (1986), Springer Berlin · Zbl 0575.00023
[14] Ruohonen, K., A note on language equations involving morphisms, Inform. process. lett., 7, 209-212, (1978) · Zbl 0385.68058
[15] Ruohonen, K., The inclusion problem for D0L languages, Elektron. informationsverarbeit. kybernetik, 15, 535-548, (1979) · Zbl 0428.68081
[16] Ruohonen, K., The decidability of the D0L-DT0L equivalence problem, J. comput. system sci., 22, 42-52, (1981) · Zbl 0491.68048
[17] Ruohonen, K., On machine characterization of nonrecursive hierarchies, Ann. univ. turkuensis ser. A I, 186, 87-101, (1984) · Zbl 0562.03023
[18] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[19] Salomaa, A., L codes and L systems with immigration. the formal language theory column, EATCS bull., 43, 124-130, (1991) · Zbl 0744.68082
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.