Abstract
A 2D string is simply a 2D array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely the number of distinct tandems, distinct quartics, and runs. First, we construct an infinite family of \(n\times n\) 2D strings with \(\varOmega (n^{3})\) distinct tandems. Second, we construct an infinite family of \(n\times n\) 2D strings with \(\varOmega (n^{2}\log n)\) distinct quartics. Third, we construct an infinite family of \(n\times n\) 2D strings with \(\varOmega (n^{2}\log n)\) runs. This resolves an open question of Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020], who asked if the number of distinct quartics and runs in an \(n\times n\) 2D string is \(\mathcal {O}(n^{2})\).
P. Gawrychowski—Partially supported by the Bekker programme of the Polish National Agency for Academic Exchange (PPN/BEK/2020/1/00444).
S. Ghazawi and G. M. Landau—Partially supported by the Israel Science Foundation grant 1475/18, and Grant No. 2018141 from the United States-Israel Binational Science Foundation (BSF).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Data Compression Conference, pp. 279–288 (1992)
Amir, A., Benson, G.: Two-dimensional periodicity in rectangular arrays. SIAM J. Comput. 27(1), 90–106 (1998)
Amir, A., Benson, G., Farach-Colton, M.: An alphabet independent approach to two dimensional pattern matching. SIAM J. Comput. 23(2), 313–323 (1995)
Amir, A., Benson, G., Farach-Colton, M.: Optimal parallel two dimensional text searching on a CREW PRAM. Inf. Comput. 144, 1–17 (1998)
Amir, A., Landau, G.M., Marcus, S., Sokol, D.: Two-dimensional maximal repetitions. In: 26th ESA, vol. 112, no. 2, pp. 1–14 (2018)
Amir, A., Landau, G.M., Marcus, S., Sokol, D.: Two-dimensional maximal repetitions. Theoret. Comput. Sci. 812, 49–61 (2020)
Amit, M., Gawrychowski, P.: Distinct squares in circular words. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 27–37. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67428-5_3
Apostolico, A., Brimkov, V.: Fibonacci arrays and their two-dimensional repetitions. Theoret. Comput. Sci. 237(1–2), 263–273 (2000)
Bannai, H.I.T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The “runs" theorem. SIAM J. Comput. 46(5), 1501–1514 (2017)
Charalampopoulos, P., Radoszewski, J., Rytter, W., Waleń, T., Zuba, W.: The number of repetitions in 2D-strings. In: 28th ESA, vol. 173, no. 32, pp. 1–18 (2020)
Cole, R., et al.: Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In: 34th FOCS, pp. 248–258 (1993)
Crochemore, M., Ilie, L.: Maximal repetitions in strings. J. Comput. Syst. Sci. 74(5), 796–807 (2008)
Crochemore, M., Ilie, L., Tinta, L.: The “runs’’ conjecture. Theoret. Comput. Sci. 412(27), 2931–2941 (2011)
Crochemore, M., et al.: The maximum number of squares in a tree. In: Kärkkäinen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol. 7354, pp. 27–40. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31265-6_3
Crochemore, M., Iliopoulos, C.S., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: Extracting powers and periods in a word from its runs structure. Theoret. Comput. Sci. 521, 29–41 (2014)
Crochemore, M., Rytter, W.: Squares, cubes, and time-space efficient string searching. Algorithmica 13, 405–425 (1995). https://doi.org/10.1007/BF01190846
Currie, J.D., Fitzpatrick, D.S.: Circular words avoiding patterns. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol. 2450, pp. 319–325. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45005-X_28
Deza, A., Franek, F., Thierry, A.: How many double squares can a string contain? Discret. Appl. Math. 180, 52–69 (2015)
Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255(1), 539–553 (2001)
Fischer, J., Holub, Š, I, T., Lewenstein, M.: Beyond the runs theorem. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 277–286. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23826-5_27
Fraenkel, A.S., Simpson, J.: How many squares can a string contain? J. Comb. Theory, Ser. A 82(1), 112–120 (1998)
Franek, F., Yang, Q.: An asymptotic lower bound for the maximal number of runs in a string. Int. J. Found. Comput. Sci. 19(1), 195–203 (2008)
Gawrychowski, P., Kociumaka, T., Rytter, W., Waleń, T.: Tight bound for the number of distinct palindromes in a tree. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 270–276. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23826-5_26
Giraud, M.: Not so many runs in strings. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 232–239. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88282-4_22
Holub, S.: Prefix frequency of lost positions. Theoret. Comput. Sci. 684, 43–52 (2017)
Ilie, L.: A simple proof that a word of length n has at most 2n distinct squares. J. Comb. Theory, Ser. A 112(1), 163–164 (2005)
Ilie, L.: A note on the number of squares in a word. Theoret. Comput. Sci. 380(3), 373–376 (2007)
Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: String powers in trees. Algorithmica 79(3), 814–834 (2017). https://doi.org/10.1007/s00453-016-0271-3
Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: 40th FOCS, pp. 596–604. IEEE Computer Society (1999)
Manea, F., Seki, S.: Square-density increasing mappings. In: Manea, F., Nowotka, D. (eds.) WORDS 2015. LNCS, vol. 9304, pp. 160–169. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23660-5_14
Matsubara, W., Kusano, K., Ishino, A., Bannai, H., Shinohara, A.: New lower bounds for the maximum number of runs in a string. In: Proceedings of the Prague Stringology Conference 2008, pp. 140–145 (2008)
Puglisi, S.J., Simpson, J., Smyth, W.F.: How many runs can a string contain? Theoret. Comput. Sci. 401(1–3), 165–171 (2008)
Rytter, W.: The number of runs in a string. Inf. Comput. 205(9), 1459–1469 (2007)
Simpson, J.: Modified Padovan words and the maximum number of runs in a word. Australas. J. Combin. 46, 129–146 (2010)
Simpson, J.: Palindromes in circular words. Theoret. Comput. Sci. 550, 66–78 (2014)
Thue, A.: Über unendliche Zeichenreihen. Norske Vid Selsk. Skr. I Mat-Nat Kl. (Christiana) 7, 1–22 (1906)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Gawrychowski, P., Ghazawi, S., Landau, G.M. (2021). Lower Bounds for the Number of Repetitions in 2D Strings. In: Lecroq, T., Touzet, H. (eds) String Processing and Information Retrieval. SPIRE 2021. Lecture Notes in Computer Science(), vol 12944. Springer, Cham. https://doi.org/10.1007/978-3-030-86692-1_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-86692-1_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86691-4
Online ISBN: 978-3-030-86692-1
eBook Packages: Computer ScienceComputer Science (R0)