Search

Your search keyword '"Crochemore, Maxime"' showing total 1,021 results
Start Over Author "Crochemore, Maxime"

Refine your results

more »

more »

more »

more »
1,021 results on '"Crochemore, Maxime"'

105. On the Size of DASG for Multiple Texts

Author

Crochemore, Maxime, Troníček, Zdeněk, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Laender, Alberto H. F., editor, and Oliveira, Arlindo L., editor

Published
2002
Full Text
View/download PDF

106. Three Heuristics for δ-Matching: δ-BM Algorithms

Author

Crochemore, Maxime, Iliopoulos, Costas S., Lecroq, Thierry, Plandowski, Wojciech, Rytter, Wojciech, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Apostolico, Alberto, editor, and Takeda, Masayuki, editor

Published
2002
Full Text
View/download PDF

108. Back-To-Front Online Lyndon Forest Construction

Author

Badkobeh, Golnaz, Crochemore, Maxime, Ellert, Jonas, Nicaud, Cyril, Badkobeh, Golnaz, Crochemore, Maxime, Ellert, Jonas, and Nicaud, Cyril

Abstract

A Lyndon word is a word that is lexicographically smaller than all of its non-trivial rotations (e.g. ananas is a Lyndon word; banana is not a Lyndon word due to its smaller rotation abanan). The Lyndon forest (or equivalently Lyndon table) identifies maximal Lyndon factors of a word, and is of great combinatoric interest, e.g. when finding maximal repetitions in words. While optimal linear time algorithms for computing the Lyndon forest are known, none of them work in an online manner. We present algorithms that compute the Lyndon forest of a word in a reverse online manner, processing the input word from back to front. We assume a general ordered alphabet, i.e. the only elementary operations on symbols are comparisons of the form less-equal-greater. We start with a naive algorithm and show that, despite its quadratic worst-case behaviour, it already takes expected linear time on words drawn uniformly at random. We then introduce a much more sophisticated algorithm that takes linear time in the worst case. It borrows some ideas from the offline algorithm by Bille et al. (ICALP 2020), combined with new techniques that are necessary for the reverse online setting. While the back-to-front approach for this computation is rather natural (see Franek and Liut, PSC 2019), the steps required to achieve linear time are surprisingly intricate. We envision that our algorithm will be useful for the online computation of maximal repetitions in words.

Published
2022
Full Text
View/download PDF

109. Back-To-Front Online Lyndon Forest Construction

Author

Golnaz Badkobeh and Maxime Crochemore and Jonas Ellert and Cyril Nicaud, Badkobeh, Golnaz, Crochemore, Maxime, Ellert, Jonas, Nicaud, Cyril, Golnaz Badkobeh and Maxime Crochemore and Jonas Ellert and Cyril Nicaud, Badkobeh, Golnaz, Crochemore, Maxime, Ellert, Jonas, and Nicaud, Cyril

Abstract

A Lyndon word is a word that is lexicographically smaller than all of its non-trivial rotations (e.g. ananas is a Lyndon word; banana is not a Lyndon word due to its smaller rotation abanan). The Lyndon forest (or equivalently Lyndon table) identifies maximal Lyndon factors of a word, and is of great combinatoric interest, e.g. when finding maximal repetitions in words. While optimal linear time algorithms for computing the Lyndon forest are known, none of them work in an online manner. We present algorithms that compute the Lyndon forest of a word in a reverse online manner, processing the input word from back to front. We assume a general ordered alphabet, i.e. the only elementary operations on symbols are comparisons of the form less-equal-greater. We start with a naive algorithm and show that, despite its quadratic worst-case behaviour, it already takes expected linear time on words drawn uniformly at random. We then introduce a much more sophisticated algorithm that takes linear time in the worst case. It borrows some ideas from the offline algorithm by Bille et al. (ICALP 2020), combined with new techniques that are necessary for the reverse online setting. While the back-to-front approach for this computation is rather natural (see Franek and Liut, PSC 2019), the steps required to achieve linear time are surprisingly intricate. We envision that our algorithm will be useful for the online computation of maximal repetitions in words.

Published
2022
Full Text
View/download PDF

110. Fast Evolutionary Chains

Author

Crochemore, Maxime, Iliopoulos, Costas S., Pinzon, Yoan J., Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hlaváč, Václav, editor, Jeffery, Keith G., editor, and Wiedermann, Jiří, editor

Published
2000
Full Text
View/download PDF

118. On compact directed acyclic word graphs

Author

Crochemore, Maxime, Vérin, Renaud, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Mycielski, Jan, editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
1997
Full Text
View/download PDF

128. Speeding up two string-matching algorithms

Author

Crochemore, Maxime, Lecroq, Thierry, Czumaj, Artur, Gasieniec, Leszek, Jarominek, Stefan, Plandowski, Wojciech, Rytter, Wojciech, Goos, Gerhard, editor, Hartmanis, Juris, editor, Finkel, Alain, editor, and Jantzen, Matthias, editor

Published
1992
Full Text
View/download PDF

130. Parallel construction of minimal suffix and factor automata

Author

Crochemore, Maxime, Rytter, Wojciech, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, and Rovan, Branislav, editor

Published
1990
Full Text
View/download PDF

131. Parallel computations on strings and arrays

Author

Crochemore, Maxime, Rytter, Wojciech, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Choffrut, Christian, editor, and Lengauer, Thomas, editor

Published
1990
Full Text
View/download PDF

145. Forty Years of Text Indexing

Author

Apostolico, Alberto, primary, Crochemore, Maxime, additional, Farach-Colton, Martin, additional, Galil, Zvi, additional, and Muthukrishnan, S., additional

Published
2013
Full Text
View/download PDF

147. Presentations of constrained systems with unconstrained positions

Author

Beal, Marie-Pierre, Crochemore, Maxime, and Fici, Gabriele

Subjects
Algorithm, Information theory -- Research, Algorithms -- Research
Abstract

We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a linear-time construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type (PFT) systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for constructing the minimal periodic forbidden blocks of a finite sequence for a given period. Index Terms--Directed acyclic word graph (DAWG), finite-memory systems, finite-state encoders, forbidden blocks, maximum transition run (MTR) codes, modulation codes, periodic-finite-type (PFT) systems, run-length limited (RLL) codes.

Published
2005

149. The Maximum Number of Squares in a Tree

Author

Crochemore, Maxime, primary, Iliopoulos, Costas S., additional, Kociumaka, Tomasz, additional, Kubica, Marcin, additional, Radoszewski, Jakub, additional, Rytter, Wojciech, additional, Tyczyński, Wojciech, additional, and Waleń, Tomasz, additional

Published
2012
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results