A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Abelian powers and repetitions in Sturmian words

Julkaisun tekijät: Fici Gabriele,Langiu Alessio,Lecroq Thierry,Lefebvre Arnaud,Mignosi Filippo,Peltomäki Jarkko,Prieur-Gaston élise
Kustantaja: Elsevier B.V.
Julkaisuvuosi: 2016
Journal: Theoretical Computer Science
Lehden akronyymi: TCS
Volyymi: 635
Sivujen määrä: 19
ISSN: 0304-3975
eISSN: 1879-2294


Richomme, Saari and Zamboni (J.~Lond.~Math.~Soc.~83:~79--95,~2011) proved that at every position of a Sturmian word starts an  abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $alpha$. By considering all possible abelian periods $m$, we recover the result of Richomme, Saari and Zamboni.

As an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_alpha)$ of a Sturmian word $s_alpha$ of angle $alpha$ as the quantity $A(s_alpha) = limsup k_{m}/m=limsup k'_{m}/m$, where $k_{m}$ (resp. $k'_{m}$) denotes the maximum exponent of an abelian power (resp.~of an abelian repetition) of abelian period $m$ (the superior limits coincide for Sturmian words). We show that $A(s_alpha)$ equals the Lagrange constant of the number $alpha$. This yields a formula for computing $A(s_alpha)$ in terms of the partial quotients of the continued fraction expansion of $alpha$. Using this formula, we prove that $A(s_alpha) geq sqrt{5}$ and that the equality holds for the Fibonacci word. We further prove that $A(s_alpha)$ is finite if and only if $alpha$ has bounded partial quotients, that is, if and only if $s_{alpha}$ is $eta$-power-free for some real number $eta$.

Concerning the infinite Fibonacci word, we prove that: emph{i}) The longest prefix that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1}+1)-2$ if $j$ is even or $F_j( F_{j+1}+F_{j-1} )-2$ if $j$ is odd, where $F_{j}$ is the $j$th Fibonacci number; emph{ii}) The minimum abelian period of any factor is a Fibonacci number.  Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words: we prove that for $jgeq 3$ the Fibonacci word $f_j$, of length $F_{j}$, has minimum abelian period equal to $F_{lfloor{j/2}
floor}$ if $j = 0, 1, 2mod{4}$ or to $F_{1+lfloor{j/2}
floor}$ if $j=3mod{4}$.

Sisäiset tekijät/toimittajat

Last updated on 2019-11-09 at 21:13