An upper bound on asymptotic repetition threshold of balanced sequences via colouring of the Fibonacci sequence

DOI10.1016/J.TCS.2024.114490MaRDI QIDQ6204547zbMATH OpenFDO

Authors L'ubomíra Dvořáková, Edita Pelantová

Publication date 28 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Fibonacci sequencereturn wordbalanced sequenceconstant gap sequencebispecial factorasymptotic critical exponentasymptotic repetition threshold

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We colour the Fibonacci sequence by suitable constant gap sequences to provide an upper bound on the asymptotic repetitive threshold of $d$-ary balanced sequences. The bound is attained for $d=2,4$ and $8$ and we conjecture that it happens for infinitely many even $d$'s. Our bound reveals an essential difference in behavior of the repetitive threshold and the asymptotic repetitive threshold of balanced sequences. The repetitive threshold of $d$-ary balanced sequences is known to be at least $1+frac1d-2$ for each $dgeq3$. In contrast, our bound implies that the asymptotic repetitive threshold of $d$-ary balanced sequences is at most $1+fraca{u}^3{2}^{d-3}$ for each $dgeq2$, where $au$ is the golden mean.

Recommendations

• Asymptotic repetitive threshold of balanced sequences
• On minimal critical exponent of balanced sequences
• On balanced sequences and their critical exponent
• On the D0L Repetition Threshold
• Repetition thresholds for subdivided graphs and trees

Cites work

• A characterization of Sturmian words by return words
• A characterization of substitutive sequences using return words
• A proof of Dejean’s conjecture
• A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
• Asymptotic repetitive threshold of balanced sequences
• Balance properties of Arnoux-Rauzy words
• Complementary symmetric Rote sequences: the critical exponent and the recurrence function
• Covering the positive integers by disjoint sets of the form \(\{[n\alpha+\beta]: n=1,2,\dots \}\)
• Critical exponent of infinite balanced words via the Pell number system
• Critical exponents of infinite balanced words
• Dejean's conjecture and Sturmian words
• Episturmian words and some constructions of de Luca and Rauzy
• Generalizations of Sturmian sequences associated with \(\boldsymbol{N}\)-continued fraction algorithms
• Languages invariant under more symmetries: overlapping factors versus palindromic richness
• Last cases of Dejean's conjecture
• On Dejean's conjecture over large alphabets
• On a Class of 2-Balanced Sequences
• On balanced sequences and their critical exponent
• On extremal properties of the Fibonacci word
• On minimal critical exponent of balanced sequences
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
• Repetitions in the Fibonacci infinite word
• Special factors, periodicity, and an application to Sturmian words
• Sur un théorème de Thue
• Symbolic Dynamics II. Sturmian Trajectories
• The repetition threshold for binary rich words
• Well-balanced sequences
• Words derivated from Sturmian words

Cited in

(1)

• The repetition threshold of episturmian sequences

This page was built for publication: An upper bound on asymptotic repetition threshold of balanced sequences via colouring of the Fibonacci sequence

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