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, (Lecture Notes in Computer Science, 71 (1979), Springer: Springer Berlin), 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, (Technical Report CU-CS-173-80 (1980), Department of Computer Science, University of Colorado at Boulder) · Zbl 0495.68069
[7] Harrison, M., Introduction to Formal Language Theory (1978), Addison-Wesley: 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: Academic Press New York · Zbl 0365.68072
[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.