On maximal repetitions of arbitrary exponent

DOI10.1016/J.IPL.2010.01.005zbMATH Open1209.68300DBLPjournals/ipl/KolpakovKO10OpenAlexW2063371253WikidataQ58064500 ScholiaQ58064500MaRDI QIDQ991771FDOQ991771

Authors Gregory Kucherov, Pascal Ochem, Roman Kolpakov 

Publication date 7 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

theory of computationcombinatorial problemsrepetitionsperiodicities

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The first two authors have shown [KK99,KK00] that the sum the exponent (and thus the number) of maximal repetitions of exponent at least 2 (also called runs) is linear in the length of the word. The exponent 2 in the definition of a run may seem arbitrary. In this paper, we consider maximal repetitions of exponent strictly greater than 1.

Recommendations

• scientific article; zbMATH DE number 21766
• scientific article; zbMATH DE number 5171552
• Fewest repetitions versus maximal-exponent powers in infinite binary words
• On the maximal exponent of the prime power divisor of integers
• THE MAXIMAL ORDER OF ITERATED MULTIPLICATIVE FUNCTIONS
• scientific article; zbMATH DE number 4051925
• The iterated exponential integers
• On the maximal length of arithmetic progressions
• On the Cycle Structure of Repeated Exponentiation Modulo a Prime Power

Cites Work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• Polynomial versus exponential growth in repetition-free binary words
• Sur un théorème de Thue
• Towards a Solution to the “Runs” Conjecture

Cited In (9)

• Optimal bounds for computing \({\alpha}\)-gapped repeats
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Title not available (Why is no real title available?)
• Searching of gapped repeats and subrepetitions in a word
• Some results on the number of periodic factors in words
• On primary and secondary repetitions in words
• The complexity of smooth words on 2-letter alphabets
• Computing maximal-exponent factors in an overlap-free word

This page was built for publication: On maximal repetitions of arbitrary exponent

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