Deciding context equivalence of binary overlap-free words in linear time

DOI10.1007/S00233-012-9382-6zbMath1279.68241OpenAlexW1980322817MaRDI QIDQ444679

Arseny M. Shur

Publication date: 16 August 2012

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00233-012-9382-6

zbMATH Keywords

word problemcontext equivalenceoverlap-free wordssyntactic monoid

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algebraic theory of languages and automata (68Q70)

Related Items (5)

On the Tree of Ternary Square-Free Words ⋮ Lengths of irreducible and delicate words ⋮ Transition property for cube-free words ⋮ Computing the \(k\)-binomial complexity of the Thue-Morse word ⋮ Subword complexity and power avoidance

Cites Work

• Unnamed Item
• Polynomial versus exponential growth in repetition-free binary words
• Overlap-free words and spectra of matrices
• Syntactic semigroups of avoided languages
• A characterization of overlap-free morphisms
• The structure of the set of cube-free $ Z$-words in a two-letter alphabet
• A linear-time algorithm to decide whether a binary word contains an overlap
• Binary Sequences which Contain no BBb
• OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
• A Characterization of the Morse Minimal Set
• WORDS AVOIDING $\frac{7}{3}$-POWERS AND THE THUE–MORSE MORPHISM

This page was built for publication: Deciding context equivalence of binary overlap-free words in linear time