Computing maximal-exponent factors in an overlap-free word

DOI10.1016/J.JCSS.2015.11.007MaRDI QIDQ899581zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Golnaz Badkobeh, Maxime Crochemore

Publication date 30 December 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://research.gold.ac.uk/id/eprint/22721/1/MaxExpFac.pdf

zbMATH Keywords

automatonperiodicityreturn wordword exponentmaximal repetitionsoverlap-free word

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• On maximal repetitions of arbitrary exponent
• Counting maximal-exponent factors in words
• Publication:4934345
• Computing the maximum exponent in a stream
• Some results on the number of periodic factors in words

Cites work

• scientific article; zbMATH DE number 1615296 (Why is no real title available?)
• scientific article; zbMATH DE number 2185638 (Why is no real title available?)
• scientific article; zbMATH DE number 3825215 (Why is no real title available?)
• A characterization of Sturmian words by return words
• A proof of Dejean’s conjecture
• A universal algorithm for sequential data compression
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Computing longest previous non-overlapping factors
• Covering a string
• Efficient seeds computation revisited
• Finite repetition threshold for large alphabets
• Last cases of Dejean's conjecture
• Maximal repetitions in strings
• On maximal repetitions of arbitrary exponent
• Sur un théorème de Thue
• The ``runs conjecture
• The number of runs in a string
• The subtree max gap problem with application to parallel string covering

Cited in

(6)

• Computing the maximum exponent in a stream
• Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
• Counting maximal-exponent factors in words
• The complexity of computing maximal word functions
• Optimal computation of overabundant words
• Efficient computation of maximal anti-exponent in palindrome-free strings

This page was built for publication: Computing maximal-exponent factors in an overlap-free word

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