A linear-time algorithm to decide whether a binary word contains an overlap

DOI10.1051/ITA/1988220201351MaRDI QIDQ3789095zbMATH OpenOpenAlexFDO

Authors Assaf Kfoury

Publication date 1988

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92303

zbMATH Keywords

linear-time algorithmoverlap-free binary words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Deciding context equivalence of binary overlap-free words in linear time
• scientific article; zbMATH DE number 512830
• scientific article; zbMATH DE number 3995072
• Overlap-free words and finite automata
• Extremal infinite overlap-free binary words

Cited in

(13)

• Growth of repetition-free words -- a review
• Pattern avoidance: themes and variations
• On the number of Abelian square-free words on four letters
• A rewriting of Fife's theorem about overlap-free words
• Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices
• Infinite words containing squares at every position
• Deciding context equivalence of binary overlap-free words in linear time
• On the context-freeness of the set of words containing overlaps
• On repetition-free binary words of minimal density
• If a DOL language is k-power free then it is circular
• Overlap-free words and finite automata
• Overlap-free words and spectra of matrices
• Polynomial versus exponential growth in repetition-free binary words

This page was built for publication: A linear-time algorithm to decide whether a binary word contains an overlap

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