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

\(k\)-overlapde Bruijn wordoverlappattern avoidancesplit 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.

Review text

A \(t\)-overlap is a finite word of the form \(xxx'\), where \(|x'|=t\) and the word \(x\) starts with \(x'\). Here \(1\)-overlaps are just usual overlaps studied since Thue's papers from the beginning of the 20th century. A split occurrence of a repetition is a word of the form \(xyz\), where \(xz\) forms the repetition; so, for example, the word \texttt{contentment} contains the factor \texttt{ntentment} which is a split occurrence of the \(2\)-overlap \texttt{ntentent}. As Ochem remarked (the proof of this statement is given in the paper for the sake of completeness), there are no infinite words over a finite alphabet which would avoid split overlaps. So, the main results of this paper are upper and lower bounds for the length of the longest word over a \(k\)-letter alphabet which avoids split \(t\)-overlaps.

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

• A note on bifix-free sequences (Corresp.)
• A proof of Dejean’s conjecture
• A Successor Rule Framework for Constructing $k$ -Ary de Bruijn Sequences and Universal Cycles
• Context-free languages and primitive words
• Finiteness and iteration conditions for semigroups
• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• 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)

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

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)