Document Open Access Logo

Rectangular Tile Covers of 2D-Strings

Authors Jakub Radoszewski , Wojciech Rytter , Juliusz Straszyński , Tomasz Waleń , Wiktor Zuba

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2022.23.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • tile cover
  • periodicity
  • efficient algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We consider tile covers of 2D-strings which are a generalization of periodicity of 1D-strings. We say that a 2D-string A is a tile cover of a 2D-string S if S can be decomposed into non-overlapping 2D-strings, each of them equal to A or to A^T, where A^T is the transpose of A. We show that all tile covers of a 2D-string of size N can be computed in 𝒪(N^{1+ε}) time for any ε > 0. We also show a linear-time algorithm for computing all 1D-strings being tile covers of a 2D-string.

Cite As Get BibTex

Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, and Wiktor Zuba. Rectangular Tile Covers of 2D-Strings. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CPM.2022.23

Author Details

Jakub Radoszewski
  • University of Warsaw, Poland
Wojciech Rytter
  • University of Warsaw, Poland
Juliusz Straszyński
  • University of Warsaw, Poland
Tomasz Waleń
  • University of Warsaw, Poland
Wiktor Zuba
  • University of Warsaw, Poland
  • CWI, Amsterdam, The Netherlands

Funding

  • Radoszewski, Jakub: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Straszyński, Juliusz: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Waleń, Tomasz: Supported by the Polish National Science Center, grant no. 2018/31/D/ST6/03991.
  • Zuba, Wiktor: Supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.

Acknowledgements

We thank Panagiotis Charalampopoulos for helpful discussions.

References

  1. Tom M. Apostol. Introduction to analytic number theory. Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, 1976. Google Scholar
  2. Alberto Apostolico, Martin Farach, and Costas S. Iliopoulos. Optimal superprimitivity testing for strings. Information Processing Letters, 39(1):17-20, 1991. URL: https://doi.org/10.1016/0020-0190(91)90056-N.
  3. Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM Journal on Computing, 46(5):1501-1514, 2017. URL: https://doi.org/10.1137/15M1011032.
  4. Dany Breslauer. An on-line string superprimitivity test. Information Processing Letters, 44(6):345-347, 1992. URL: https://doi.org/10.1016/0020-0190(92)90111-8.
  5. Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Computing covers of 2D-strings. In Pawel Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, volume 191 of LIPIcs, pages 12:1-12:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CPM.2021.12.
  6. Maxime Crochemore, Costas S. Iliopoulos, and Maureen Korda. Two-dimensional prefix string matching and covering on square matrices. Algorithmica, 20(4):353-373, 1998. URL: https://doi.org/10.1007/PL00009200.
  7. Antoine Deza, Frantisek Franek, and Adrien Thierry. How many double squares can a string contain? Discrete Applied Mathematics, 180:52-69, 2015. URL: https://doi.org/10.1016/j.dam.2014.08.016.
  8. Aviezri S. Fraenkel and Jamie Simpson. How many squares can a string contain? Journal of Combinatorial Theory, Series A, 82(1):112-120, 1998. URL: https://doi.org/10.1006/jcta.1997.2843.
  9. Pawel Gawrychowski, Samah Ghazawi, and Gad M. Landau. Lower bounds for the number of repetitions in 2D strings. In Thierry Lecroq and Hélène Touzet, editors, String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, volume 12944 of Lecture Notes in Computer Science, pages 179-192. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-86692-1_15.
  10. Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323-350, 1977. URL: https://doi.org/10.1137/0206024.
  11. Roman M. Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pages 596-604. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814634.
  12. M. Lothaire. Combinatorics on words, Second Edition. Cambridge Mathematical Library. Cambridge University Press, 1997. Google Scholar
  13. Alexandru Popa and Andrei Tanasescu. An output-sensitive algorithm for the minimization of 2-dimensional string covers. In Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, volume 11436 of Lecture Notes in Computer Science, pages 536-549. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-14812-6_33.
  14. Adrien Thierry. A proof that a word of length n has less than 1.5n distinct squares, 2020. URL: https://doi.org/10.48550/ARXIV.2001.02996.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact