Repetitive strings are not context-free
Ross, Rockford ; Winklmann, Karl
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982), p. 191-199 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1982__16_3_191_0,
     author = {Ross, Rockford and Winklmann, Karl},
     title = {Repetitive strings are not context-free},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {16},
     year = {1982},
     pages = {191-199},
     mrnumber = {686912},
     zbl = {0489.68071},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1982__16_3_191_0}
}

Ross, Rockford; Winklmann, Karl. Repetitive strings are not context-free. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 16 (1982) pp. 191-199. http://gdmltest.u-ga.fr/item/ITA_1982__16_3_191_0/

1. J. M. Autebert, J. Beauquier, L. Boasson and M. Nivat, Quelques problèmes ouverts en théorie des langages algébriques, R.A.I.R.O. Informatique Théorique, Vol. 13,(4), 1979, pp. 363-378. | Numdam | MR 556958 | Zbl 0434.68056

2. D. R. Bean, A. Ehrenfeucht and G. F. Mcnulty, Avoidable Patierns in Strings of Symbols, Pacific Journal of Mathematics, Vol. 85, (2), 1979, pp. 261-294. | MR 574919 | Zbl 0428.05001

3. J. Berstel, Sur les mots sans carré définis par un morphisme, A. MAURER, Ed., Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 71, Springer-Verlag, 1979, pp. 16-25. | MR 573232 | Zbl 0425.20046

4. C. H. Braunholtz, Solution to Problem 5030, American Math. Monthly, Vol. 70, 1963, pp. 675-676. | MR 1532217

5. S. A. Greibach, Eraseable Context-Free Languages, Information and Control, Vol. 4, 1975, pp. 301-306. | MR 386358 | Zbl 0317.68059

6. M. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978. | MR 526397 | Zbl 0411.68058

7. G. A. Hedlund, Remarks on the Work of Axel Thue on Sequences, Nordisk Matematisk Tidskrift, Vol. 15, 1967, pp. 148-150. | MR 228875 | Zbl 0153.33101

8. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

9. G. Hotz and R. Ross, LL (k)-and LR (k)-Invarianz von Kontextfreien Grammatike unter einer Transformation auf Greibach-Normalform, Elektronische Informationsverarbeitung und Kybernetik, Vol. 15, (1/2), 1979, pp. 73-86. | MR 542003 | Zbl 0426.68065

10. P. A. B. Pleasants, Nonrepetitive Sequence, Proc. Cambridge Philosophical Society, Vol. 68, 1970, pp. 267-274. | Zbl 0237.05010

11. R. Ross Grammar Transformations Based on Regular Decompositions of Context-Free Derivations, Dissertation, Computer Science Department, Washington State University, Pullman, WA. 1978.

12. R. Ross, G. Hotz and D. Benson, A General Greibach-Normal-Form transformation, Technical Report CS-78-048, Computer Science Department, Washington State University, Pullman, WA. 1978.

13. A. Thue, Über Unendliche Zeichenreih, Norske Videnskabers Selskabs Skrifter Mat.-Nat. K1. (Kristiania), Nr. 7, 1906, S. 1-22. | JFM 39.0283.01

14. A. Thue, Über die Gegenseitige Lage Gleicher Teile Gewisser Zeichenre, Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl. (Kristiania), Nr. 1, 1912, S. 1-67. | JFM 44.0462.01