Large-scale detection of repetitions

Area of Science:

• Theoretical Computer Science
• Discrete Mathematics
• Computational Stringology

Background:

• Combinatorics on words has a long history, with early work focusing on constructing infinite strings without repetitions.
• Computing repetitions in strings is a fundamental problem in computational stringology.
• Current methods compute repetitions via maximal periodicities (runs) in linear time, but require costly preprocessing.

Purpose of the Study:

• To investigate alternative methods for computing string repetitions.
• To explore if repetitions can be found more efficiently, commensurate with the output size.
• To potentially reduce the computational overhead for pattern discovery in strings.

Main Methods:

• The study reviews existing algorithms for computing repetitions and maximal periodicities (runs).
• It analyzes the computational complexity and preprocessing requirements of current approaches.
• It proposes exploring new computational strategies for pattern identification.

Main Results:

• Existing linear-time algorithms for runs necessitate global data structures (e.g., suffix array, LCP array).
• The computational effort for these methods is disproportionate to the typically small number of runs in a string.
• The paper highlights the need for more output-sensitive algorithms.

Conclusions:

• There is a need for more efficient algorithms in computational stringology.
• Future research should focus on methods where computation scales with output size.
• This could lead to faster discovery of repetitions and other string regularities.