Lower bounds for the number of repetitions in 2D strings

DOI10.1007/978-3-030-86692-1_15MaRDI QIDQ2146138zbMATH OpenOpenAlexFDO

Authors Samah Ghazawi, Gad M. Landau, Paweł Gawrychowski

Publication date 15 June 2022

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

zbMATH Keywords

2D stringsquarticsrunstandems

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Two-dimensional maximal repetitions
• Optimal discovery of repetitions in 2D
• Fibonacci arrays and their two-dimensional repetitions
• Two-dimensional maximal repetitions
• scientific article; zbMATH DE number 7651094

Cites work

• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Distinct squares in circular words
• Episturmian words and some constructions of de Luca and Rauzy
• 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?
• scientific article; zbMATH DE number 5717191 (Why is no real title available?)
• scientific article; zbMATH DE number 1948509 (Why is no real title available?)
• Maximal repetitions in strings
• Not So Many Runs in Strings
• Optimal parallel two dimensional text searching on a CREW PRAM
• Palindromes in circular words
• Prefix frequency of lost positions
• Square-density increasing mappings
• Squares, cubes, and time-space efficient string searching
• String powers in trees
• The ``runs conjecture
• The ``runs theorem
• The maximum number of squares in a tree
• The number of repetitions in 2D-strings
• The number of runs in a string
• Two-dimensional maximal repetitions
• Two-dimensional maximal repetitions
• Two-Dimensional Periodicity in Rectangular Arrays
• Universal reconstruction of a string

Cited in

(8)

• Fibonacci arrays and their two-dimensional repetitions
• Two-dimensional maximal repetitions
• The number of repetitions in 2D-strings
• Two-dimensional Fibonacci words: tandem repeats and factor complexity
• Exact and inexact search for 2d side-sharing tandems
• On the complexity of indeterminate strings matching
• Optimal bounds for distinct quartics
• Searching 2D-strings for matching frames

This page was built for publication: Lower bounds for 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 Q2146138)