On the subword complexity of square-free DOL languages. (English) Zbl 0481.68073


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Berstel, J., Sur LES mots sans carré définis par un morphisme, (), 16-25 · Zbl 0425.20046
[2] Berstel, J., Mots sans carré et morphismes iterés, Discrete math., 29, 3, 235-244, (1979) · Zbl 0444.20050
[3] Brzozowski, J.A.; Culik, K.; Gabrielian, A., Classification of noncounting events, J. comput. system sci., 5, 41-53, (1971) · Zbl 0241.94050
[4] Ehrenfeucht, A.; Lee, K.P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. comput. sci., 1, 59-76, (1975) · Zbl 0316.68043
[5] Ehrenfeucht, A.; Rozenberg, G., On the structure of polynomially bounded DOL systems, Fund. informaticae, 2, 187-197, (1979) · Zbl 0452.68075
[6] Ehrenfeucht, A.; Rozenberg, G., On subword complexities of homomorphic images of languages, () · Zbl 0495.68069
[7] Harrison, M., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[8] Istrail, S., On irreducible languages and nonrational numbers, Bull. soc. math. roumanie, 21, 301-308, (1977) · Zbl 0374.68053
[9] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
[10] A. Salomaa, Morphisms on free monoids and language theory, in: R. Book, Ed., Formal Language Theory: Perspectives and Open Problems (Academic Press, New York) to appear.
[11] Thue, A., Über unendliche zeichenreihen, Norske vid. selsk. skr. I mat.-nat. kl., 7, 1-22, (1906) · JFM 39.0283.01
[12] Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichenreichen, Norske vid. selsk. skr. I mat.-nat. kl., 1, 1-67, (1912) · JFM 44.0462.01
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.