The number of repetitions in 2D-strings

DOI10.4230/LIPICS.ESA.2020.32MaRDI QIDQ5874500zbMATH OpenFDO

Authors Panagiotis Charalampopoulos, Wiktor Zuba, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2006.15999

zbMATH Keywords

squarequarticrun2D-run

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Lower bounds for the number of repetitions in 2D strings
• Two-dimensional maximal repetitions
• Optimal discovery of repetitions in 2D
• A New Periodicity Lemma
• Two-dimensional maximal repetitions

Cites work

• scientific article; zbMATH DE number 432822 (Why is no real title available?)
• scientific article; zbMATH DE number 5717191 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 7651094 (Why is no real title available?)
• scientific article; zbMATH DE number 7651099 (Why is no real title available?)
• 2D Lyndon words and applications
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• A characterization of the squares in a Fibonacci string
• A note on the number of squares in a word
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Algorithms on Strings
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• An optimal algorithm for computing the repetitions in a word
• Analysis of Maximal Repetitions in Strings
• Computing all distinct squares in linear time for integer alphabets
• Extracting powers and periods in a word from its runs structure
• Fibonacci arrays and their two-dimensional repetitions
• How many double squares can a string contain?
• How many runs can a string contain?
• How many squares can a string contain?
• Internal dictionary matching
• Internal pattern matching queries in a text and applications
• Jewels of Stringology
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Maximal repetitions in strings
• Not So Many Runs in Strings
• On the density of Lyndon roots in factors
• On-line construction of suffix trees
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Optimal discovery of repetitions in 2D
• Repetition Detection in a Dynamic String
• Simple and flexible detection of contiguous repeats using a suffix tree
• Squares, cubes, and time-space efficient string searching
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The ``runs conjecture
• The ``runs theorem
• The number of runs in a string
• The total run length of a word
• Two-dimensional maximal repetitions
• Two-dimensional maximal repetitions
• Uniqueness Theorems for Periodic Functions

Cited in

(3)

• Exact and inexact search for 2d side-sharing tandems
• Two-dimensional Fibonacci words: tandem repeats and factor complexity
• Lower bounds for the number of repetitions in 2D strings

This page was built for publication: The number of repetitions in 2D-strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874500)