Document Open Access Logo

Two-Dimensional Maximal Repetitions

Authors Amihood Amir, Gad M. Landau, Shoshana Marcus, Dina Sokol

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.2.pdf
  • Filesize: 483 kB
  • 14 pages

Document Identifiers

Author Details

Amihood Amir
  • Bar Ilan University, Ramat-Gan, 52900, Israel
Gad M. Landau
  • University of Haifa, Haifa 31905, Israel, and, NYU Tandon School of Engineering, New York University, Six MetroTech Center, Brooklyn, NY 11201, USA
Shoshana Marcus
  • Kingsborough Community College of the City University of New York, 2001 Oriental Boulevard, Brooklyn, NY 11235, USA
Dina Sokol
  • Brooklyn College of the City University of New York, 2900 Bedford Avenue, Brooklyn, NY, 11210, USA

Funding

  • Amir, Amihood: Partially supported by the Israel Science Foundation grant 571/14 and Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).
  • Landau, Gad M.: Partially supported by the Israel Science Foundation grant 571/14 and Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).
  • Sokol, Dina: Partially supported by Grant No. 2014028 from the United States-Israel Binational Science Foundation (BSF).

Cite As Get BibTex

Amihood Amir, Gad M. Landau, Shoshana Marcus, and Dina Sokol. Two-Dimensional Maximal Repetitions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.2

Abstract

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in a matrix. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions in a matrix. The algorithm is efficient and straightforward, with runtime O(n^2 log n log log n+ rho log n), where n^2 is the size of the input, and rho is the number of 2D repetitions in the output.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
  • Theory of computation → Design and analysis of algorithms
Keywords
  • pattern matching algorithms
  • repetitions
  • periodicity
  • two-dimensional

Metrics

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

References

  1. A. Amir and G. Benson. Two-dimensional periodicity in rectangular arrays. SIAM J. Comput., 27(1):90-106, 1998. URL: http://dx.doi.org/10.1137/S0097539795298321.
  2. A. Amir, G. M. Landau, M. Lewenstein, and D. Sokol. Dynamic text and static pattern matching. ACM Trans. Algorithms, 3(2):19, 2007. URL: http://dx.doi.org/10.1145/1240233.1240242.
  3. A. Apostolico and V. E. Brimkov. Fibonacci arrays and their two-dimensional repetitions. Theor. Comput. Sci., 237(1-2):263-273, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(98)00182-0.
  4. A. Apostolico and V. E. Brimkov. Optimal discovery of repetitions in 2d. Discrete Applied Mathematics, 151(1-3):5-20, 2005. URL: http://dx.doi.org/10.1016/j.dam.2005.02.019.
  5. N. Bacquey. Primitive roots of bi-periodic infinite pictures. In Words 2015, 2015. Google Scholar
  6. H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. A new characterization of maximal repetitions by Lyndon trees. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 562-571, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.38.
  7. H. Bannai, T. I, S. Inenaga, Y. Nakashima, M. Takeda, and K. Tsuruta. The "runs" theorem. SIAM J. Comput., 46(5):1501-1514, 2017. URL: http://dx.doi.org/10.1137/15M1011032.
  8. M. Crochemore, L. Gasieniec, R. Hariharan, S. Muthukrishnan, and W. Rytter. A constant time optimal parallel algorithm for two-dimensional pattern matching. SIAM J. Comput., 27(3):668-681, 1998. URL: http://dx.doi.org/10.1137/S0097539795280068.
  9. M. Crochemore, L. Ilie, and W. Rytter. Repetitions in strings: Algorithms and combinatorics. Theor. Comput. Sci., 410(50):5227-5235, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.08.024.
  10. M. Crochemore and W. Rytter. Sqares, cubes, and time-space efficient string searching. Algorithmica, 13(5):405-425, 1995. URL: http://dx.doi.org/10.1007/BF01190846.
  11. G. Gamard and G. Richomme. Coverability in two dimensions. In A. H. Dediu, E. Formenti, C. Martín-Vide, and B. Truthe, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, volume 8977 of Lecture Notes in Computer Science, pages 402-413. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-15579-1_31.
  12. G. Gamard, G. Richomme, J. Shallit, and T. J. Smith. Periodicity in rectangular arrays. Inf. Process. Lett., 118:58-63, 2017. URL: http://dx.doi.org/10.1016/j.ipl.2016.09.011.
  13. D. Gusfield and J. Stoye. Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci., 69(4):525-546, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.03.004.
  14. R. M. Karp, R. E. Miller, and A. L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing, May 1-3, 1972, Denver, Colorado, USA, pages 125-136, 1972. URL: http://dx.doi.org/10.1145/800152.804905.
  15. T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen. Internal pattern matching queries in a text and applications. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532-551, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.36.
  16. R. M. Kolpakov and G. Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 596-604. IEEE Computer Society, 1999. URL: http://dx.doi.org/10.1109/SFFCS.1999.814634.
  17. S. Marcus and D. Sokol. 2d Lyndon words and applications. Algorithmica, 77(1):116-133, 2017. URL: http://dx.doi.org/10.1007/s00453-015-0065-z.
  18. E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, 1995. URL: http://dx.doi.org/10.1007/BF01206331.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact