On context constrained squares and repetitions in a string

A. Apostolico

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

  • Volume: 18, Issue: 2, page 147-159
  • ISSN: 0988-3754

How to cite

top

Apostolico, A.. "On context constrained squares and repetitions in a string." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 18.2 (1984): 147-159. <http://eudml.org/doc/92203>.

@article{Apostolico1984,
author = {Apostolico, A.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {repetitions in a string; repetition roots; square-free recognition; linear time},
language = {eng},
number = {2},
pages = {147-159},
publisher = {EDP-Sciences},
title = {On context constrained squares and repetitions in a string},
url = {http://eudml.org/doc/92203},
volume = {18},
year = {1984},
}

TY - JOUR
AU - Apostolico, A.
TI - On context constrained squares and repetitions in a string
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1984
PB - EDP-Sciences
VL - 18
IS - 2
SP - 147
EP - 159
LA - eng
KW - repetitions in a string; repetition roots; square-free recognition; linear time
UR - http://eudml.org/doc/92203
ER -

References

top
  1. 1. A. THUE, Uber Die Gegenseitige Lage Gleicher Teile Gewisser Zeichenreichen, Skr. Vid.-Kristiana I. Mat. Naturv. Klasse, Vol. 1, 1912, pp. 1-67 JFM44.0462.01
  2. 2. M. MAIN and R. LORENTZ, An O (n log n) Algorithm for Finding Repetition in a String. T.R. 79-056, Comp. Sc. Dept., Washington State Univ., Pullman, 1972. 
  3. 3. M. CROCHEMORE, An Optimal Algorithm for Computing the Repetitions in a Word, Information Processing Letters, Vol. 12, 1981, pp. 244-250. Zbl0467.68075MR632873
  4. 4. A. APOSTOLICO and F. P. PREPARATA, Optimal Off-Line Detection of Repetitions in a String, Theoretical Computer Science, Vol. 22, 1983, pp. 237-315. Zbl0497.68052MR693062
  5. 5. A. LENTIN and M. P. SCHUTZEMBERGER, A Combinatorial Problem in the Theory of Free Monoids, in Combinatorial Mathematics and its Applications, University of North Carolina Press, N.C., 1969, pp. 128-144. Zbl0221.20076
  6. 6. A. APOSTOLICO and F. P. PREPARATA, A Structure for the Statistics of All Substrings of a Textstring With or Without Overlap. Proceedings of the 2nd World Conference on Mathematics at the Service of Man, Las Palmas (Canary Islands), 1982. Zbl0503.68064
  7. 7. E. M. MCCREIGHT, A Space Economical Suffix Tree Construction Algorithm, J. of the ACM, Vol. 23, 1976, pp. 262-272. Zbl0329.68042MR413594
  8. 8. R. C. LYNDON and M. P. SCHUTZEMBERGER, The Equation aM = bN cP in a Free Group, Michigan Mathemat. Journal, Vol. 9, 1962, pp. 289-298 Zbl0106.02204MR162838
  9. 9. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, MA, 1974. Zbl0326.68005MR413592
  10. 10. P. WEINER, Linear Pattern Matching Algorithms, Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1-11 MR441032
  11. 11. D. E. KNUTH, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, MA, 1973. Zbl0302.68010MR445948

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.