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

Tiivistelmä

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