We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. If k m denotes the maximal exponent of an abelian repetition of period m, we prove that limsup km/m>=5?? for any Sturmian word, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word 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. This allows us to give an exact formula for the smallest abelian periods of the Fibonacci finite words. More precisely, we prove that for j >= 3, the Fibonacci word f j has abelian period equal to F n , where n=?j/2? if j=0,1,2mod4, or n=1+?j/2? if j=3mod4.

Abelian repetitions in Sturmian words

Langiu Alessio;
2013

Abstract

We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. If k m denotes the maximal exponent of an abelian repetition of period m, we prove that limsup km/m>=5?? for any Sturmian word, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word 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. This allows us to give an exact formula for the smallest abelian periods of the Fibonacci finite words. More precisely, we prove that for j >= 3, the Fibonacci word f j has abelian period equal to F n , where n=?j/2? if j=0,1,2mod4, or n=1+?j/2? if j=3mod4.
2013
Inglese
Developments in Language Theory
Developments in Language Theory
7907
227
238
978-3-642-38771-5
http://www.scopus.com/record/display.url?eid=2-s2.0-84884143834&origin=inward
Sì, ma tipo non specificato
18-21/06/2013
Paris
Sturmian word
6
none
Fici, Gabriele; Langiu, Alessio; Lecroq, Thierry; Lefebvre, Arnaud; Mignosi, Filippo; Prieurgaston, Élise
273
info:eu-repo/semantics/conferenceObject
04 Contributo in convegno::04.01 Contributo in Atti di convegno
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/269893
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact