Abelian powers and repetitions in Sturmian words

Gabriele Fici, Alessio Langiu, Élise Prieur-Gaston, Jarkko Peltomäki, Thierry Lecroq, Filippo Mignosi, Arnaud Lefebvre

Risultato della ricerca: Article

8 Citazioni (Scopus)

Abstract

Richomme, Saari and Zamboni (2011) [39] 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 α. 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α) of a Sturmian word sα of angle α as the quantity A(sα)=limsupkm/m=limsupkm′/m, where km (resp. km′) 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α) equals the Lagrange constant of the number α. This yields a formula for computing A(sα) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A(sα)≥5 and that the equality holds for the Fibonacci word. We further prove that A(sα) is finite if and only if α has bounded partial quotients, that is, if and only if sα is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period Fj, j>1, has length Fj(Fj+1+Fj−1+1)−2 if j is even or Fj(Fj+1+Fj−1)−2 if j is odd, where Fj is the jth Fibonacci number; 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 j≥3 the Fibonacci word fj, of length Fj, has minimum abelian period equal to F⌊j/2⌋ if j=0,1,2mod4 or to F1+⌊j/2⌋ if j=3mod4.
Lingua originaleEnglish
pagine (da-a)16-34
Numero di pagine19
RivistaTheoretical Computer Science
Volume635
Stato di pubblicazionePublished - 2016

Fingerprint

Sturmian Words
Exponent
Lame number
Critical Exponents
Quotient
If and only if
Analogue
Partial
Angle
Continued Fraction Expansion
Fractional Powers
Computing
Prefix
Repetition
Lagrange
Equality
Odd
Denote

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Fici, G., Langiu, A., Prieur-Gaston, É., Peltomäki, J., Lecroq, T., Mignosi, F., & Lefebvre, A. (2016). Abelian powers and repetitions in Sturmian words. Theoretical Computer Science, 635, 16-34.

Abelian powers and repetitions in Sturmian words. / Fici, Gabriele; Langiu, Alessio; Prieur-Gaston, Élise; Peltomäki, Jarkko; Lecroq, Thierry; Mignosi, Filippo; Lefebvre, Arnaud.

In: Theoretical Computer Science, Vol. 635, 2016, pag. 16-34.

Risultato della ricerca: Article

Fici, G, Langiu, A, Prieur-Gaston, É, Peltomäki, J, Lecroq, T, Mignosi, F & Lefebvre, A 2016, 'Abelian powers and repetitions in Sturmian words', Theoretical Computer Science, vol. 635, pagg. 16-34.
Fici G, Langiu A, Prieur-Gaston É, Peltomäki J, Lecroq T, Mignosi F e altri. Abelian powers and repetitions in Sturmian words. Theoretical Computer Science. 2016;635:16-34.
Fici, Gabriele ; Langiu, Alessio ; Prieur-Gaston, Élise ; Peltomäki, Jarkko ; Lecroq, Thierry ; Mignosi, Filippo ; Lefebvre, Arnaud. / Abelian powers and repetitions in Sturmian words. In: Theoretical Computer Science. 2016 ; Vol. 635. pagg. 16-34.
@article{b91f629dedd844399782db115d39aacd,
title = "Abelian powers and repetitions in Sturmian words",
abstract = "Richomme, Saari and Zamboni (2011) [39] 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 α. 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α) of a Sturmian word sα of angle α as the quantity A(sα)=limsupkm/m=limsupkm′/m, where km (resp. km′) 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α) equals the Lagrange constant of the number α. This yields a formula for computing A(sα) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A(sα)≥5 and that the equality holds for the Fibonacci word. We further prove that A(sα) is finite if and only if α has bounded partial quotients, that is, if and only if sα is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period Fj, j>1, has length Fj(Fj+1+Fj−1+1)−2 if j is even or Fj(Fj+1+Fj−1)−2 if j is odd, where Fj is the jth Fibonacci number; 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 j≥3 the Fibonacci word fj, of length Fj, has minimum abelian period equal to F⌊j/2⌋ if j=0,1,2mod4 or to F1+⌊j/2⌋ if j=3mod4.",
keywords = "Abelian period, Abelian power, Computer Science (all), Critical exponent, Lagrange constant, Sturmian word, Theoretical Computer Science",
author = "Gabriele Fici and Alessio Langiu and {\'E}lise Prieur-Gaston and Jarkko Peltom{\"a}ki and Thierry Lecroq and Filippo Mignosi and Arnaud Lefebvre",
year = "2016",
language = "English",
volume = "635",
pages = "16--34",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

TY - JOUR

T1 - Abelian powers and repetitions in Sturmian words

AU - Fici, Gabriele

AU - Langiu, Alessio

AU - Prieur-Gaston, Élise

AU - Peltomäki, Jarkko

AU - Lecroq, Thierry

AU - Mignosi, Filippo

AU - Lefebvre, Arnaud

PY - 2016

Y1 - 2016

N2 - Richomme, Saari and Zamboni (2011) [39] 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 α. 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α) of a Sturmian word sα of angle α as the quantity A(sα)=limsupkm/m=limsupkm′/m, where km (resp. km′) 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α) equals the Lagrange constant of the number α. This yields a formula for computing A(sα) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A(sα)≥5 and that the equality holds for the Fibonacci word. We further prove that A(sα) is finite if and only if α has bounded partial quotients, that is, if and only if sα is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period Fj, j>1, has length Fj(Fj+1+Fj−1+1)−2 if j is even or Fj(Fj+1+Fj−1)−2 if j is odd, where Fj is the jth Fibonacci number; 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 j≥3 the Fibonacci word fj, of length Fj, has minimum abelian period equal to F⌊j/2⌋ if j=0,1,2mod4 or to F1+⌊j/2⌋ if j=3mod4.

AB - Richomme, Saari and Zamboni (2011) [39] 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 α. 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α) of a Sturmian word sα of angle α as the quantity A(sα)=limsupkm/m=limsupkm′/m, where km (resp. km′) 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α) equals the Lagrange constant of the number α. This yields a formula for computing A(sα) in terms of the partial quotients of the continued fraction expansion of α. Using this formula, we prove that A(sα)≥5 and that the equality holds for the Fibonacci word. We further prove that A(sα) is finite if and only if α has bounded partial quotients, that is, if and only if sα is β-power-free for some real number β. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period Fj, j>1, has length Fj(Fj+1+Fj−1+1)−2 if j is even or Fj(Fj+1+Fj−1)−2 if j is odd, where Fj is the jth Fibonacci number; 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 j≥3 the Fibonacci word fj, of length Fj, has minimum abelian period equal to F⌊j/2⌋ if j=0,1,2mod4 or to F1+⌊j/2⌋ if j=3mod4.

KW - Abelian period

KW - Abelian power

KW - Computer Science (all)

KW - Critical exponent

KW - Lagrange constant

KW - Sturmian word

KW - Theoretical Computer Science

UR - http://hdl.handle.net/10447/191865

UR - http://www.journals.elsevier.com/theoretical-computer-science/

M3 - Article

VL - 635

SP - 16

EP - 34

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -