Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T08:10:20.909Z Has data issue: false hasContentIssue false
  • English
  • Français

On the number of squares in partial words

Published online by Cambridge University Press:  11 February 2010

Vesa Halava ,
Tero Harju  and
Tomi Kärki
Vesa Halava
Affiliation:
Department of Mathematics and Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected], [email protected], [email protected]
Tero Harju
Affiliation:
Department of Mathematics and Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected], [email protected], [email protected]
Tomi Kärki
Affiliation:
Department of Mathematics and Turku Centre for Computer Science, University of Turku, 20014 Turku, Finland; [email protected], [email protected], [email protected] Institute of Mathematics, University of Liège, Grand Traverse 12 (B 37), 4000 Liège, Belgium.
Get access

Abstract

The theorem of Fraenkel and Simpson states that the maximum number of distinct squares that a word w of length n can contain is less than 2n. This is based on the fact that no more than two squares can have their last occurrences starting at the same position. In this paper we show that the maximum number of the last occurrences of squares per position in a partial word containing one hole is 2k, where k is the size of the alphabet. Moreover, we prove that the number of distinct squares in a partial word with one hole and of length n is less than 4n, regardless of the size of the alphabet. For binary partial words, this upper bound can be reduced to 3n.

Keywords

Squarepartial wordtheorem of Fraenkel and Simpson.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 1: Special issue dedicated to the 12th "Journées Montoises d'Informatique Théorique" , January 2010 , pp. 125 - 138
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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.
Berstel, J. and Boasson, L., Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999) 135–141. CrossRef
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 http://www.uncg.edu/cmp/research/freeness/distinctsquares.pdf
Crochemore, M. and Rytter, W., Squares, cubes, and time-space efficient string searching. Algorithmica 13 (1995) 405–425. CrossRef
Fraenkel, A.S. and Simpson, J., How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120. CrossRef
Halava, V., Harju, T., Kärki, T. and Séébold, P., Overlap-freeness in infinite partial words. Theoret. Comput. Sci. 410 (2009) 943–948. CrossRef
Halava, V., Harju, T. and Kärki, T., Square-free partial words. Inform. Process. Lett. 108 (2008) 290–292. CrossRef
Ilie, L., A simple proof that a word of length n has at most 2n distinct squares. J. Combin. Theory Ser. A 112 (2005) 163–164. CrossRef
Ilie, L., A note on the number of squares in a word. Theoret. Comput. Sci. 380 (2007) 373–376. CrossRef
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).
Manea, F. and Mercaş, R., Freeness of partial words. Theoret. Comput. Sci. 389 (2007) 265–277. CrossRef
A. Thue, Über unendliche Zeichenreihen. Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 7 (1906) 1–22.
A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1 (1912) 1–67.