آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,559 |
| تعداد مشاهده مقاله | 1,666,882 |
| تعداد دریافت فایل اصل مقاله | 1,556,985 |
The Length of the Longest Sequence of Consecutive FS-double Squares in a Word | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 8، دوره 9، شماره 2، شهریور 2024، صفحه 263-277 اصل مقاله (441.5 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2022.27917.1395 | ||
| نویسندگان | ||
| Maithilee Patawar* 1؛ Kalpesh Kapoor2 | ||
| 1Department of Computer Science & Engineering, Indian Institute of Technology Guwahati, India | ||
| 2Department of Mathematics, Indian Institute of Technology Guwahati, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Distinct squares؛ FS-double squares؛ Repetitions؛ Word combinatorics | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 661 تعداد دریافت فایل اصل مقاله: 2,182 |
||