On the number of squares in partial words
Vesa Halava; Tero Harju; Tomi Kärki
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 44, Issue: 1, page 125-138
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications: Proceedings of SETA'98, edited by C. Ding, T. Helleseth and H. Niederreiter. Springer, London (1999) 1–16.
- J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci.218 (1999) 135–141.
- F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2007).
- F. Blanchet-Sadri, R. Mercaş and G. Scott, Counting distinct squares in partial words, in Proceedings of the 12th International Conference on Automata and Formal Languages (AFL 2008), edited by E. Csuhaj-Varjú and Z. Ésik. Balatonfüred, Hungary (2008) 122–133. Also available at URIhttp://www.uncg.edu/cmp/research/freeness/distinctsquares.pdf
- M. Crochemore and W. Rytter, Squares, cubes, and time-space efficient string searching. Algorithmica13 (1995) 405–425.
- A.S. Fraenkel and J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A82 (1998) 112–120.
- V. Halava, T. Harju, T. Kärki and P. Séébold, Overlap-freeness in infinite partial words. Theoret. Comput. Sci.410 (2009) 943–948.
- V. Halava, T. Harju and T. Kärki, Square-free partial words. Inform. Process. Lett.108 (2008) 290–292.
- L. Ilie, A simple proof that a word of length n has at most 2n distinct squares. J. Combin. Theory Ser. A112 (2005) 163–164.
- L. Ilie, A note on the number of squares in a word. Theoret. Comput. Sci.380 (2007) 373–376.
- M. Lothaire, Combinatorics on Words. Encyclopedia of Mathematics 17, Addison-Wesley (1983).
- M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications 90, Cambridge University Press (2002).
- F. Manea and R. Mercaş, Freeness of partial words. Theoret. Comput. Sci.389 (2007) 265–277.
- A. Thue, Über unendliche Zeichenreihen. Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania7 (1906) 1–22.
- A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania1 (1912) 1–67.