Repetitive strings are not context-free

Rockford Ross; Karl Winklmann

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1982)

  • Volume: 16, Issue: 3, page 191-199
  • ISSN: 0988-3754

How to cite

top

Ross, Rockford, and Winklmann, Karl. "Repetitive strings are not context-free." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 16.3 (1982): 191-199. <http://eudml.org/doc/92161>.

@article{Ross1982,
author = {Ross, Rockford, Winklmann, Karl},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {3},
pages = {191-199},
publisher = {EDP-Sciences},
title = {Repetitive strings are not context-free},
url = {http://eudml.org/doc/92161},
volume = {16},
year = {1982},
}

TY - JOUR
AU - Ross, Rockford
AU - Winklmann, Karl
TI - Repetitive strings are not context-free
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1982
PB - EDP-Sciences
VL - 16
IS - 3
SP - 191
EP - 199
LA - eng
UR - http://eudml.org/doc/92161
ER -

References

top
  1. 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. Zbl0434.68056MR556958
  2. 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. Zbl0428.05001MR574919
  3. 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. Zbl0425.20046MR573232
  4. 4. C. H. BRAUNHOLTZ, Solution to Problem 5030, American Math. Monthly, Vol. 70, 1963, pp. 675-676. MR1532217
  5. 5. S. A. GREIBACH, Eraseable Context-Free Languages, Information and Control, Vol. 4, 1975, pp. 301-306. Zbl0317.68059MR386358
  6. 6. M. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, 1978. Zbl0411.68058MR526397
  7. 7. G. A. HEDLUND, Remarks on the Work of Axel Thue on Sequences, Nordisk Matematisk Tidskrift, Vol. 15, 1967, pp. 148-150. Zbl0153.33101MR228875
  8. 8. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. Zbl0426.68001MR645539
  9. 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. Zbl0426.68065MR542003
  10. 10. P. A. B. PLEASANTS, Nonrepetitive Sequence, Proc. Cambridge Philosophical Society, Vol. 68, 1970, pp. 267-274. Zbl0237.05010
  11. 11. R. ROSSGrammar Transformations Based on Regular Decompositions of Context-Free Derivations, Dissertation, Computer Science Department, Washington State University, Pullman, WA. 1978. 
  12. 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. 13. A. THUE, Über Unendliche Zeichenreih, Norske Videnskabers Selskabs Skrifter Mat.-Nat. K1. (Kristiania), Nr. 7, 1906, S. 1-22. JFM39.0283.01
  14. 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. JFM44.0462.01

NotesEmbed ?

top

You must be logged in to post comments.