On the context-freeness of the set of words containing overlaps
From MaRDI portal
(Redirected from Publication:845966)
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.
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 -free binary words
- Periodicity algorithms and a conjecture on overlaps in partial words
Cites work
- scientific article; zbMATH DE number 3912631 (Why is no real title available?)
- scientific article; zbMATH DE number 3932372 (Why is no real title available?)
- scientific article; zbMATH DE number 3932412 (Why is no real title available?)
- scientific article; zbMATH DE number 3770980 (Why is no real title available?)
- scientific article; zbMATH DE number 512830 (Why is no real title available?)
- scientific article; zbMATH DE number 1973372 (Why is no real title available?)
- scientific article; zbMATH DE number 3995072 (Why is no real title available?)
- scientific article; zbMATH DE number 808803 (Why is no real title available?)
- scientific article; zbMATH DE number 3238653 (Why is no real title available?)
- A linear-time algorithm to decide whether a binary word contains an overlap
- A result about languages concerning paperfolding sequences
- An “Interchange Lemma” for Context-Free Languages
- Analytic models and ambiguity of context-free languages
- Automata calculating the complexity of automatic sequences
- Binary words containing infinitely many overlaps
- Canonical positions for the factors in paperfolding sequences
- Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
- Enumeration of factors in the Thue-Morse word
- Enumeration of irreducible binary words
- On the base-dependence of sets of numbers recognizable by finite automata
- On the structure of the counting function of sparse context-free languages.
- On the subword complexity of iteratively generated infinite words.
- Reconnaissabilité des substitutions et complexité des suites automatiques
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Subword complexity of a generalized Thue-Morse word
- Suites algébriques, automates et substitutions
- The Morse sequence and iterated morphisms
- The subword complexity of fixed points of binary uniform morphisms
- Transcendence of formal power series with rational coefficients
- Unending chess, symbolic dynamics and a problem in semi-groups
Cited in
(6)- An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity Algorithms
- OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
- scientific article; zbMATH DE number 3912631 (Why is no real title available?)
- 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)
