Source author record

Thierry Lecroq

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

ResearcherUnclaimed source record

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

Catalog footprint

Research overview

7works

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

Fast 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}$ . Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $σ$ and a Parikh vector $\mathcal{P}$ , returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(σ+p)$ , where $p$ is the norm of $\mathcal{P}$ , i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$ , for any given norm $p$ . Finally, we give an $O(n^2)$ -time offline randomized algorithm for computing all the abelian runs of $w$ . Its deterministic counterpart runs in $O(n^2\logσ)$ time.

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}$ .

preprint2013arXiv

Algorithms for Computing Abelian Periods of Words

Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $σ$ can have $Θ(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times σ)$ using $O(n \times σ)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$ .

preprint2010arXiv

The Exact String Matching Problem: a Comprehensive Experimental Evaluation

This paper addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, data compression, information retrieval, computational biology and chemistry. Since 1970 more than 80 string matching algorithms have been proposed, and more than 50% of them in the last ten years. In this note we present a comprehensive list of all string matching algorithms and present experimental results in order to compare them from a practical point of view. From our experimental evaluation it turns out that the performance of the algorithms are quite different for different alphabet sizes and pattern length.

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.

Thierry Lecroq

Research overview

Is this your work?

7 publications

Abelian Powers and Repetitions in Sturmian Words

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

Fast Computation of Abelian Runs

Online Computation of Abelian Runs

Abelian Repetitions in Sturmian Words

Algorithms for Computing Abelian Periods of Words

The Exact String Matching Problem: a Comprehensive Experimental Evaluation

See the researcher in context

Building this map preview