Source author record

Élise Prieur-Gaston

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics Data Structures and Algorithms math.CO math.NT

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Abelian Powers and Repetitions in Sturmian Words

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 $α$ . vAs 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_α) = 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_α)$ 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_α) \geq \sqrt{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 $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

preprint2015arXiv

A Note on Easy and Efficient Computation of Full Abelian Periods of a Word

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$ -time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.

preprint2015arXiv

Online Computation of Abelian Runs

Given a word $w$ and a Parikh vector $\mathcal{P}$ , an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$ . We give an algorithm that finds all the abelian runs of period $\mathcal{P}$ in a word of length $n$ in time $O(n\times |\mathcal{P}|)$ and space $O(σ+|\mathcal{P}|)$ .

preprint2013arXiv

Abelian Repetitions in Sturmian Words

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. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$ , 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\geq 3$ , the Fibonacci word $f_j$ has abelian period equal to $F_n$ , where $n = \lfloor{j/2}\rfloor$ if $j = 0, 1, 2\mod{4}$ , or $n = 1 + \lfloor{j/2}\rfloor$ if $j = 3\mod{4}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.