Optimal discovery of repetitions in 2D

DOI10.1016/j.dam.2005.02.019zbMath1101.68501OpenAlexW2039815064MaRDI QIDQ2573235

Alberto Apostolico, Valentin E. Brimkov

Publication date: 7 November 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.02.019

zbMATH Keywords

Pattern discoveryPattern matchingDesign and analysis of algorithms2D arrayTandem repetition

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Pattern recognition, speech recognition (68T10)

Related Items (5)

Unnamed Item ⋮ Unnamed Item ⋮ Double string tandem repeats ⋮ Motif patterns in 2D ⋮ Two-dimensional maximal repetitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural properties of the string statistics problem
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• Optimal parallel detection of squares in strings
• Fibonacci arrays and their two-dimensional repetitions
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences
• Plane digitization and related combinatorial problems
• Transducers and repetitions
• On a conjecture on bidimensional words.
• Local configurations in a discrete plane
• An O(n log n) algorithm for finding all repetitions in a string
• Optimal Parallel Searching an Array for Certain Repetitions
• Optimal parallel pattern matching in strings
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Alphabet-Independent Two-Dimensional Witness Computation
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String

This page was built for publication: Optimal discovery of repetitions in 2D