Avoidance of split overlaps

DOI10.1016/J.DISC.2020.112176MaRDI QIDQ2214038zbMATH OpenOpenAlexFDO

Authors Daniel Gabric, Xiao Feng Zhong, Jeffrey Shallit

Publication date 4 December 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

overlappattern avoidancede Bruijn word\(k\)-overlapsplit occurrence

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

Recommendations

• scientific article; zbMATH DE number 512830
• scientific article; zbMATH DE number 4035171
• OVERLAP-FREE WORDS AND THUE-MORSE SEQUENCES
• Overpals, underlaps, and underpals
• Avoiding squares and overlaps over the natural numbers

Cites work

• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Successor Rule Framework for Constructing $k$ -Ary de Bruijn Sequences and Universal Cycles
• A note on bifix-free sequences (Corresp.)
• A proof of Dejean’s conjecture
• Context-free languages and primitive words
• Finiteness and iteration conditions for semigroups
• Last cases of Dejean's conjecture
• Repetition avoidance in circular factors
• Sur un théorème de Thue
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Uniqueness Theorems for Periodic Functions

Cited in

(3)

• Sets of pictures avoiding overlaps
• Avoiding overlaps in pictures
• Avoiding squares and overlaps over the natural numbers

This page was built for publication: Avoidance of split overlaps

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