Abstract
In this paper, we investigate the number of positions that do not start a square, the number of square occurrences, and the number of distinct squares in binary partial words. Letting σ h (n) be the maximum number of positions not starting a square for binary partial words with h holes of length n, we show that limσ h (n)/n = 15/31 provided the limit of h/n is zero. Letting γ h (n) be the minimum number of square occurrences in a binary partial word of length n with h holes, we show, under some condition on h, that limγ h (n)/n = 103/187. Both limits turn out to match with the known limits for binary full words. We also bound the difference between the maximum number of distinct squares in a binary partial word and that of a binary full word by (2h − 1)(n + 2), where n is the length and h is the number of holes. This allows us to find a simple proof of the known 3n upper bound in a one-hole binary partial word using the completions of such a partial word.
This material is based upon work supported by the National Science Foundation under Grant No. DMS–1060775.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press, Boca Raton, FL (2008)
Blanchet-Sadri, F., Mercaş, R.: A note on the number of squares in a partial word with one hole. RAIRO-Theoretical Informatics and Applications 43, 767–774 (2009)
Blanchet-Sadri, F., Mercaş, R., Scott, G.: Counting distinct squares in partial words. Acta Cybernetica 19, 465–477 (2009)
Fraenkel, A.S., Simpson, R.J.: How many squares must a binary sequence contain? Electronic Journal of Combinatorics 2, R2 (1995)
Fraenkel, A.S., Simpson, R.J.: How many squares can a string contain? Journal of Combinatorial Theory, Series A 82, 112–120 (1998)
Halava, V., Harju, T., Kärki, T.: On the number of squares in partial words. RAIRO-Theoretical Informatics and Applications 44, 125–138 (2010)
Harju, T., Kärki, T., Nowotka, D.: The number of positions starting a square in binary words. Electronic Journal of Combinatorics 18, P6 (2011)
Ilie, L.: A simple proof that a word of length n has at most 2n distinct squares. Journal of Combinatorial Theory, Series A 112, 163–164 (2005)
Ilie, L.: A note on the number of squares in a word. Theoretical Computer Science 380, 373–376 (2007)
Kucherov, G., Ochem, P., Rao, M.: How many square occurrences must a binary sequence contain? Electronic Journal of Combinatorics 10, R12 (2003)
Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997)
Ochem, P., Rao, M.: Minimum frequencies of occurrences of squares and letters in infinite words. In: JM 2008, 12ièmes Journées Montoises d’Informatique Théorique, Mons, Belgium (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blanchet-Sadri, F., Jiao, Y., Machacek, J.M. (2012). Squares in Binary Partial Words. In: Yen, HC., Ibarra, O.H. (eds) Developments in Language Theory. DLT 2012. Lecture Notes in Computer Science, vol 7410. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31653-1_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-31653-1_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31652-4
Online ISBN: 978-3-642-31653-1
eBook Packages: Computer ScienceComputer Science (R0)