Repetitive perhaps, but certainly not boring
From MaRDI portal
(Redirected from Publication:1583539)
In this paper some of the work done on repetitions in strings is surveyed, especially that of an algorithmic nature. Several open problems are described and conjectures formulated about some of them.
Recommendations
Cites work
- A characterization of the squares in a Fibonacci string
- Abelian squares are avoidable on 4 letters
- Algorithms on Strings, Trees and Sequences
- All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
- An O(n log n) algorithm for finding all repetitions in a string
- An on-line string superprimitivity test
- An optimal algorithm for computing the repetitions in a word
- An optimal algorithm to compute all the covers of a string
- Avoidable patterns in strings of symbols
- Beatty Sequences, Continued Fractions, and Certain Shift Operators
- Covering a string
- Descriptions of the Characteristic Sequence of an Irrational
- Efficient detection of quasiperiodicities in strings
- scientific article; zbMATH DE number 2185637 (Why is no real title available?)
- scientific article; zbMATH DE number 3162927 (Why is no real title available?)
- scientific article; zbMATH DE number 3991618 (Why is no real title available?)
- scientific article; zbMATH DE number 1333603 (Why is no real title available?)
- scientific article; zbMATH DE number 1052825 (Why is no real title available?)
- scientific article; zbMATH DE number 1361493 (Why is no real title available?)
- scientific article; zbMATH DE number 3375509 (Why is no real title available?)
- On cube-free \(\omega\)-words generated by binary morphisms
- On the computational power of pushdown automata
- Open Problems in Pattern Avoidance
- Optimal off-line detection of repetitions in a string
- Optimal superprimitivity testing for strings
- Simple and flexible detection of contiguous repeats using a suffix tree
- Some combinatorial properties of Sturmian words
- Strongly non-repetitive sequences and progression-free sets
- The exact number of squares in Fibonacci words
- The subtree max gap problem with application to parallel string covering
- Uniqueness Theorems for Periodic Functions
Cited in
(14)- Repetitions in strings: algorithms and combinatorics
- Computing regularities in strings: a survey
- Experimental evaluation of algorithms for computing quasiperiods
- Approximate cover of strings
- The number of runs in a string
- Can we recover the cover?
- Strongly qth Power–Free Strings
- scientific article; zbMATH DE number 3982538 (Why is no real title available?)
- On the structure of run-maximal strings
- A Heuristic For Computing Repeats With A Factor Oracle: Application To Biological Sequences
- Quasi-periodicity under mismatch errors
- Are three squares impossible?
- The ``runs theorem
- String Covering: A Survey
This page was built for publication: Repetitive perhaps, but certainly not boring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583539)
