A linear-time algorithm to decide whether a binary word contains an overlap
Kfoury, A. J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 135-145 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1988__22_2_135_0,
     author = {Kfoury, A. J.},
     title = {A linear-time algorithm to decide whether a binary word contains an overlap},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {22},
     year = {1988},
     pages = {135-145},
     mrnumber = {951335},
     zbl = {0645.68087},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1988__22_2_135_0}
}

Kfoury, A. J. A linear-time algorithm to decide whether a binary word contains an overlap. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) pp. 135-145. http://gdmltest.u-ga.fr/item/ITA_1988__22_2_135_0/

1.J. Berstel, Some Recent Results on Squarefree Words Proc. of Symposium on Theoretical Aspects of Computer Science, 11-13 April 1984 , Paris. | MR 773306 | Zbl 0582.68042

2. M. Crochemore, Linear Searching for a Square in a Word, Bulletin of EATCS, No. 24, Oct. 1984, pp. 66-72. | MR 707557

3. A. J. Kfoury, Square-Free and Overlap-Free Words, Technical Report, Department of Computer Science, Boston University, 1985.

4. M. Lothaire, Combinatorics on Words, Addison-Wesley, 1983. | MR 675953 | Zbl 0514.20045

5. A. Resttvo and S. Salemi, Overlap Free Words on Two Symbols, in Automata on Infinité Words, Nivat and Perrin Ed., LNCS 192, Springer-Verlag, 1985, pp. 198-206. | MR 814744 | Zbl 0572.20038

6. A. Salomaa, Jewels of Formal Language Theory, Computer Science Press, 1981. | MR 618124 | Zbl 0487.68064