The Length of the Longest Sequence of Consecutive FS-double Squares in a Word

Document Type : Original paper

Authors

1 Department of Computer Science & Engineering, Indian Institute of Technology Guwahati, India

2 Department of Mathematics, Indian Institute of Technology Guwahati, India

Abstract

A square is a concatenation of two identical words, and a word $w$ is said to have a square $yy$ if $w$ can be written as $xyyz$ for some words $x$ and $z$. It is known that the ratio of the number of distinct squares in a word to its length is less than two, and any location of a word could begin with two distinct squares which are appearing in the word for the last time. A square whose first location starts with the last occurrence of two distinct squares is an FS-double square. We explore and identify the conditions under which a sequence of locations in a word starts with FS-double squares. We first find the structure of a word that begins with two consecutive FS-double squares and obtain its properties that enable us to extend the sequence of FS-double squares. It is proved that the length of the longest sequence of consecutive FS-double squares in a word of length $n$ is at most $\frac{n}{7}$. We show that the squares in the longest sequence of consecutive FS-double squares are conjugates.

Keywords

Main Subjects

References

[1] H. Bai, F. Franek, and W.F. Smyth, The new periodicity lemma revisited, Discrete Appl. Math. 212 (2016), 30–36.  https://doi.org/10.1016/j.dam.2016.05.003
[2] J. Berstel and D. Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007), no. 3, 996–1022.  https://doi.org/10.1016/j.ejc.2005.07.019
[3] F. Blanchet-Sadri and S. Osborne, Constructing words with high distinct square densities, arXiv preprint arXiv:1708.06462 (2017), 1–15.
[4] S. Brlek and S. Li, On the number of squares in a finite word, arXiv preprint arXiv:2204.10204 (2022), 1–13.
[5] M. Crochemore, An optimal algorithm for computing the repetitions in a word, Inform. Process. Lett. 12 (1981), no. 5, 244–250.  https://doi.org/10.1016/0020-0190(81)90024-7
[6] M. Crochemore and W. Rytter, Jewels of Stringology: Text Algorithms, World Scientific, 2002.
[7] A. Deza, F. Franek, and M. Jiang, A $d$-step approach for distinct squares in strings, Annual Symposium on Combinatorial Pattern Matching, Springer, 2011, pp. 77–89.  https://doi.org/10.1007/978-3-642-21458-5_9
[8] A. Deza, F. Franek, and M. Jiang, A computational framework for determining square-maximal strings., Stringology, Citeseer, 2012, pp. 111–119.
[9] A. Deza, F. Franek, and A. Thierry, How many double squares can a string contain?, Discrete Appl. Math. 180 (2015), 52–69.  https://doi.org/10.1016/j.dam.2014.08.016
[10] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965), no. 1, 109–114.
[11] A.S. Fraenkel and J. Simpson, How many squares can a string contain?, J. Combin. Theory, Ser. A 82 (1998), no. 1, 112–120.  https://doi.org/10.1006/jcta.1997.2843
[12] F. Franek and M. Liut, Computational substantiation of the $d$-step conjecture for distinct squares revisited, Prague Stringology Conference 2021, 2021, pp. 41–51.
[13] L. Ilie, A simple proof that a word of length $n$ has at most $2n$ distinct squares, J. Combin. Theory, Ser. A 112, no. 1, 163–164.  https://doi.org/10.1016/j.jcta.2005.01.006
[14] L. Ilie, A note on the number of squares in a word, Theoret. Comput. Sci. 380 (2007), no. 3, 373–376. https://doi.org/10.1016/j.tcs.2007.03.025
[15] M. Lothaire, Applied Combinatorics on Words, vol. 105, Cambridge University Press, Cambridge, 2005.
[16] F. Manea and S. Seki, Square-density increasing mappings, International Conference on Combinatorics on Words, Springer, 2015, pp. 160–169.
[17] M. Patawar and K. Kapoor, Characterization of dense patterns having distinct squares, Conference on Algorithms and Discrete Applied Mathematics, Springer, 2021, pp. 397–409.
[18] A. Thierry, A proof that a word of length $n$ has less than $1.5n$ distinct squares, arXiv preprint arXiv:2001.02996 (2020), 1–30.
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 263-277

Files

Share

How to cite

Statistics