Author name cluster

Arnaud Lefebvre

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2018 Journal Article

A survey of string orderings and their application to the Burrows–Wheeler transform

Jacqueline W. Daykin
Richard Groult
Yannick Guesnet
Thierry Lecroq
Arnaud Lefebvre
Martine Léonard
Élise Prieur-Gaston

For over 20 years the data clustering properties and applications of the efficient Burrows–Wheeler transform have been researched. Lexicographic suffix-sorting is induced during the transformation, and more recently a new direction has considered alternative ordering strategies for suffix arrays and thus the transforms. In this survey we look at these distinctly ordered bijective and linear transforms. For arbitrary alphabets we discuss the V-BWT derived from V-order and the D-BWT based on lex-extension order. The binary case yields a pair of transforms, the binary Rouen B-BWT, defined using binary block order. Lyndon words are relevant to implementing the original transform; the new transforms are defined for analogous structures: V-words, indeterminate Lyndon words, and B-words, respectively. There is plenty of scope for further non-lexicographic transforms as indicated in the conclusion.

Details DOI

TCS Journal 2016 Journal Article

Abelian powers and repetitions in Sturmian words

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

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 α ) = lim sup k m / m = lim sup 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 α ) ≥ 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 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 f j, of length F j, has minimum abelian period equal to F ⌊ j / 2 ⌋ if j = 0, 1, 2 mod 4 or to F 1 + ⌊ j / 2 ⌋ if j = 3 mod 4.

Details DOI

TCS Journal 2016 Journal Article

Binary block order Rouen Transform

Jacqueline W. Daykin
Richard Groult
Yannick Guesnet
Thierry Lecroq
Arnaud Lefebvre
Martine Léonard
Élise Prieur-Gaston

We introduce bijective Burrows–Wheeler type transforms for binary strings. 1 The original method by Burrows and Wheeler [4] is based on lexicographic order for general alphabets, and the transform is defined to be the last column of the ordered BWT matrix. This new approach applies binary block order, B-order, which yields not one, but twin transforms: one based on Lyndon words, the other on a repetition of Lyndon words. These binary B-BWT transforms are constructed here for B-words, analogous structures to Lyndon words. A key computation in the transforms is the application of a linear-time suffix-sorting technique, such as [18, 21, 22, 27], to sort the cyclic rotations of a binary input string into their B-order. Moreover, like the original lexicographic transform, we show that computing the B-BWT inverses is also achieved in linear time by using straightforward combinatorial arguments.

Details DOI

TCS Journal 2016 Journal Article

Fast computation of abelian runs

Gabriele Fici
Tomasz Kociumaka
Thierry Lecroq
Arnaud Lefebvre
Élise Prieur-Gaston

Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period 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 P, returns all the abelian runs of period P in w in time O ( n ) and space O ( σ + p ), where p is the norm of 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 ( n p ), 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.

Details DOI

TCS Journal 2004 Journal Article

Linear-time computation of local periods

Jean-Pierre Duval
Roman Kolpakov
Gregory Kucherov
Thierry Lecroq
Arnaud Lefebvre

We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.

Details DOI

MFCS Conference 2003 Conference Paper

Linear-Time Computation of Local Periods

Jean-Pierre Duval
Roman Kolpakov
Gregory Kucherov
Thierry Lecroq
Arnaud Lefebvre

Abstract We present a linear-time algorithm for computing all local periods of a given word. This subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the Critical Factorization Theorem.

Details