Back to Search
Start Over
Extremal overlap-free and extremal $��$-free binary words
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
Abstract
- An overlap-free (or $��$-free) word $w$ over a fixed alphabet $��$ is extremal if every word obtained from $w$ by inserting a single letter from $��$ at any position contains an overlap (or a factor of exponent at least $��$, respectively). We find all lengths which admit an extremal overlap-free binary word. For every extended real number $��$ such that $2^+\leq��\leq 8/3$, we show that there are arbitrarily long extremal $��$-free binary words.
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Formal Languages and Automata Theory (cs.FL)
FOS: Mathematics
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
Combinatorics (math.CO)
68R15
Computer Science::Formal Languages and Automata Theory
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........921b33e8cb4ec2c985b0122f02e9c8a1
- Full Text :
- https://doi.org/10.48550/arxiv.2006.10152