Optimality of some algorithms to detect quasiperiodicities

DOI10.1016/J.TCS.2010.04.039MaRDI QIDQ986546zbMATH OpenOpenAlexFDO

Authors Richard Groult, Gwénaël Richomme

Publication date 11 August 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.04.039

zbMATH Keywords

quasiperiodicityFibonacci wordsrepetitions in words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• scientific article; zbMATH DE number 5800967
• scientific article; zbMATH DE number 1438873
• Experimental evaluation of algorithms for computing quasiperiods
• Publication:4939600
• scientific article; zbMATH DE number 848086
• scientific article; zbMATH DE number 1855595
• Optimal detection of a recurring tuple of reference fragments in a quasiperiodic sequence
• scientific article; zbMATH DE number 5887089
• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• An Optimal Algorithm for Detecting Pseudo-squares

Cites work

• scientific article; zbMATH DE number 1615296 (Why is no real title available?)
• scientific article; zbMATH DE number 5604107 (Why is no real title available?)
• scientific article; zbMATH DE number 5604127 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1151822 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1792103 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 1400047 (Why is no real title available?)
• A characterization of the squares in a Fibonacci string
• Algorithms on Strings
• 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
• Computing the cover array in linear time
• Efficient detection of quasiperiodicities in strings
• How many squares can a string contain?
• On extremal properties of the Fibonacci word
• Optimal superprimitivity testing for strings
• Quasiperiodic Sturmian words and morphisms
• Quasiperiodic and Lyndon episturmian words
• Testing string superprimitivity in parallel
• The exact number of squares in Fibonacci words

Cited in

(8)

• Computing regularities in strings: a survey
• Overlapping factors in words
• scientific article; zbMATH DE number 5800967 (Why is no real title available?)
• scientific article; zbMATH DE number 1400047 (Why is no real title available?)
• Crochemore's partitioning on weighted strings and applications
• scientific article; zbMATH DE number 1759538 (Why is no real title available?)
• First-hit analysis of algorithms for computing quadratic irregularity
• Experimental evaluation of algorithms for computing quasiperiods

This page was built for publication: Optimality of some algorithms to detect quasiperiodicities

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