Abelian Powers and Repetitions in Sturmian Words

Autor: Alessio Langiu, Élise Prieur-Gaston, Gabriele Fici, Filippo Mignosi, Thierry Lecroq, Jarkko Peltomäki, Arnaud Lefebvre
Přispěvatelé: Università degli studi di Palermo - University of Palermo, Department of Informatics [King's College London], King‘s College London, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Dipartimento di Informatica [Italy] (DI), Università degli Studi dell'Aquila (UNIVAQ), Fici, G., Langiu, A., Lecroq, T., Lefebvre, A., Mignosi, F., Peltomäki, J., Prieur-Gaston, É., Dipartimento di Energia, ingegneria dell'Informazione e modelli Matematici [Palermo] (DEIM), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
FOS: Computer and information sciences
Fibonacci number
General Computer Science
Discrete Mathematics (cs.DM)
Formal Languages and Automata Theory (cs.FL)
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Combinatorics
FOS: Mathematics
Mathematics - Combinatorics
[INFO]Computer Science [cs]
Number Theory (math.NT)
0101 mathematics
Abelian group
Continued fraction
Fibonacci word
ComputingMilieux_MISCELLANEOUS
Quotient
Mathematics
Mathematics - Number Theory
ta111
010102 general mathematics
Computer Science (all)
Sturmian word
Abelian period
Abelian power
Critical exponent
Lagrange constant
010201 computation theory & mathematics
Bounded function
Exponent
Combinatorics (math.CO)
Computer Science::Formal Languages and Automata Theory
Computer Science - Discrete Mathematics
Zdroj: Theoretical computer science 635 (2016): 16–34. doi:10.1016/j.tcs.2016.04.039
info:cnr-pdr/source/autori:Fici, Gabriele; Langiu, Alessio; Lecroq, Thierry; Lefebvre, Arnaud; Mignosi, Filippo; Peltomäki, Jarkko; Prieur-Gaston, Élise/titolo:Abelian powers and repetitions in Sturmian words/doi:10.1016%2Fj.tcs.2016.04.039/rivista:Theoretical computer science/anno:2016/pagina_da:16/pagina_a:34/intervallo_pagine:16–34/volume:635
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2016, 635, pp.16-34. ⟨10.1016/j.tcs.2016.04.039⟩
Fici, G, Langiu, A, Lecroq, T, Lefebvre, A, Mignosi, F, Peltomäki, J & Prieur-Gaston, É 2016, ' Abelian powers and repetitions in Sturmian words ', Theoretical Computer Science . https://doi.org/10.1016/j.tcs.2016.04.039
ISSN: 1879-2294
0304-3975
DOI: 10.1016/j.tcs.2016.04.039
Popis: 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$. vAs 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 $\beta$-power-free for some real number $\beta$. Concerning the infinite Fibonacci word, we prove that: 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; 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
Comment: To appear in Theoretical Computer Science
Databáze: OpenAIRE
Externí odkaz: