Back to Search Start Over

Avoidance of split overlaps

Authors :
Gabric, Daniel
Shallit, Jeffrey
Publication Year :
2020
Publisher :
arXiv, 2020.

Abstract

We generalize Axel Thue's familiar definition of overlaps in words, and show that there are no infinite words containing split occurrences of these generalized overlaps. Along the way we prove a useful theorem about repeated disjoint occurrences in words -- an interesting natural variation on the classical de Bruijn sequences.

Subjects

Subjects :
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
FOS: Mathematics
Mathematics - Combinatorics
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
Combinatorics (math.CO)
Computer Science::Formal Languages and Automata Theory
Computer Science - Discrete Mathematics

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....775e64cc89795695cc653a3e62238768
Full Text :
https://doi.org/10.48550/arxiv.2002.01968
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details