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

DOI10.1051/ita/1988220201351zbMath0645.68087OpenAlexW177169205MaRDI QIDQ3789095

A. J. 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

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

Related Items (13)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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