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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.