On the context-freeness of the set of words containing overlaps

DOI10.1016/J.IPL.2006.11.008zbMATH Open1184.68330arXivmath/0610067OpenAlexW2065040823MaRDI QIDQ845966FDOQ845966

Authors: Narad Rampersad 

Publication date: 29 January 2010

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

Abstract: We show that the set of binary words containing overlaps is not unambiguously context-free and that the set of ternary words containing overlaps is not context-free. We also show that the set of binary words that are not subwords of the Thue-Morse word is not unambiguously context-free.

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

Recommendations

• Overlap-freeness in infinite partial words
• Overlap-free words and finite automata
• An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms
• Deciding context equivalence of binary overlap-free words in linear time
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
• scientific article; zbMATH DE number 3995072
• scientific article; zbMATH DE number 8008
• Extremal overlap-free and extremal \(\beta\)-free binary words
• Periodicity algorithms and a conjecture on overlaps in partial words

zbMATH Keywords

formal languagesThue-Morse wordoverlap-free words

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• Suites algébriques, automates et substitutions
• Transcendence of formal power series with rational coefficients
• On the base-dependence of sets of numbers recognizable by finite automata
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumeration of factors in the Thue-Morse word
• On the structure of the counting function of sparse context-free languages.
• Analytic models and ambiguity of context-free languages
• Title not available (Why is that?)
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Subword complexity of a generalized Thue-Morse word
• Title not available (Why is that?)
• A linear-time algorithm to decide whether a binary word contains an overlap
• Enumeration of irreducible binary words
• Unending chess, symbolic dynamics and a problem in semi-groups
• Title not available (Why is that?)
• The Morse sequence and iterated morphisms
• Automata calculating the complexity of automatic sequences
• Title not available (Why is that?)
• The subword complexity of fixed points of binary uniform morphisms
• Canonical positions for the factors in paperfolding sequences
• An “Interchange Lemma” for Context-Free Languages
• A result about languages concerning paperfolding sequences
• Title not available (Why is that?)
• On the subword complexity of iteratively generated infinite words.
• Binary words containing infinitely many overlaps

Cited In (6)

• An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms
• OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
• Title not available (Why is that?)
• Overlapping words, codes, disjunctivity and density of languages
• Maximum number of distinct and nonequivalent nonstandard squares in a word
• Overlap-freeness in infinite partial words

This page was built for publication: On the context-freeness of the set of words containing overlaps

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