×
Ehrenfeucht, A.; Rozenberg, G.

On the separating power of EOL systems. (English) Zbl 0512.68059

RAIRO, Inf. Théor. 17, 13-22 (1983).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0512.68059

Cited in 1 Review
Cited in 2 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

EOL language; context-free language; pure squares; square-free words; square words
PDF BibTeX XML Cite
\textit{A. Ehrenfeucht} and \textit{G. Rozenberg}, RAIRO, Inf. Théor. 17, 13--22 (1983; Zbl 0512.68059)
Full Text: EuDML

References:

[1] 1. J. M. AUTEBERT, J. BEAUQUIER, L. BOASSON and M. NIVAT, Quelques problèmes ouverts en théorie des langages algébrique, RAIRO Informatique Théorique, vol. 13, 1979, p. 363-379. Zbl0434.68056 MR556958 · Zbl 0434.68056
[2] 2. J. BERSTEL, Sur les mots sans carré définis par un morphism, Lecture Notes in Computer Science, Springer-Verlag, vol. 71, 1979, p. 16-25. Zbl0425.20046 MR573232 · Zbl 0425.20046
[3] 3. D. R. BEAN, A. EHRENFEUCHT and G. F. MCNULTY, Avoidable patterns in strings of symbols, Pacific Journal of Mathematics, vol. 85, n^\circ 2, 1979, p. 261-294. Zbl0428.05001 MR574919 · Zbl 0428.05001
[4] 4. A. EHRENFEUCHT and G. ROZENBERG, On the subword complexity of square-free DOL languages, Theoretical Computer Science, to appear. Zbl0481.68073 MR632668 · Zbl 0481.68073
[5] 5. M. HARRISON, Introduction to formal language theory, Addison-Wesley, Reading, Massachusetts, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[6] 6. J. VAN LEEUWEN, The tape complexity of context independent developmental languages, Journal of Computer and System Sciences, vol. 11, 1975, p. 203-211. Zbl0314.68017 MR381397 · Zbl 0314.68017
[7] 7. G. ROZENBERG and A. SALOMAA, The mathematical theory of L System, Academic Press, London, New York, 1980. Zbl0508.68031 MR561711 · Zbl 0508.68031
[8] 8. A. SALOMAA, Morphisms on free monoids and language theory, in Book, R (ed.), Formal language theory: perspectives and open problems, Academic Press, London, New York, to appear.
[9] 9. A. SALOMAA, Jewels of formal language theory, Computer Press, Potomac, Md., to appear. MR618124 · Zbl 0487.68064
[10] 10. A. THUE, Ueber unendliche Zeichenreihen, Norsk. Vid. Selsk. Skr. I Mat.-Nat. Kl., n^\circ 7, 1906, p. 1-22. JFM39.0283.01 · JFM 39.0283.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.