18 Search Results for "Nicaud, Cyril"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.31
Delaunay Triangulations with Predictions

Authors: Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.
Cite as

Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos. Delaunay Triangulations with Predictions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ITCS.2026.31,
  author =	{Cabello, Sergio and Chan, Timothy M. and Giannopoulos, Panos},
  title =	{{Delaunay Triangulations with Predictions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31},
  URN =		{urn:nbn:de:0030-drops-253186},
  doi =		{10.4230/LIPIcs.ITCS.2026.31},
  annote =	{Keywords: Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.60
Fast and Memory-Efficient BWT Construction of Repetitive Texts Using Lyndon Grammars

Authors: Jannik Olbrich

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The Burrows-Wheeler Transform (BWT) serves as the basis for many important sequence indexes. On very large datasets (e.g. genomic databases), classical BWT construction algorithms are often infeasible because they usually need to have the entire dataset in main memory. Fortunately, such large datasets are often highly repetitive. It can thus be beneficial to compute the BWT from a compressed representation. We propose an algorithm for computing the BWT via the Lyndon straight-line program, a grammar based on the standard factorization of Lyndon words. Our algorithm can also be used to compute the extended BWT (eBWT) of a multiset of sequences. We empirically evaluate our implementation and find that we can compute the BWT and eBWT of very large datasets faster and/or with less memory than competing methods.
Cite as

Jannik Olbrich. Fast and Memory-Efficient BWT Construction of Repetitive Texts Using Lyndon Grammars. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 60:1-60:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{olbrich:LIPIcs.ESA.2025.60,
  author =	{Olbrich, Jannik},
  title =	{{Fast and Memory-Efficient BWT Construction of Repetitive Texts Using Lyndon Grammars}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{60:1--60:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.60},
  URN =		{urn:nbn:de:0030-drops-245286},
  doi =		{10.4230/LIPIcs.ESA.2025.60},
  annote =	{Keywords: Burrows-Wheeler Transform, Grammar compression}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.38
The Complexity of Separability for Semilinear Sets and Parikh Automata

Authors: Elias Rojas Collins, Chris Köcher, and Georg Zetzsche

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In a separability problem, we are given two sets K and L from a class 𝒞, and we want to decide whether there exists a set S from a class 𝒮 such that K ⊆ S and S ∩ L = ∅. In this case, we speak of separability of sets in 𝒞 by sets in 𝒮. We study two types of separability problems. First, we consider separability of semilinear sets (i.e. subsets of ℕ^d for some d) by sets definable by quantifier-free monadic Presburger formulas (or equivalently, the recognizable subsets of ℕ^d). Here, a formula is monadic if each atom uses at most one variable. Second, we consider separability of languages of Parikh automata by regular languages. A Parikh automaton is a machine with access to counters that can only be incremented, and have to meet a semilinear constraint at the end of the run. Both of these separability problems are known to be decidable with elementary complexity. Our main results are that both problems are coNP-complete. In the case of semilinear sets, coNP-completeness holds regardless of whether the input sets are specified by existential Presburger formulas, quantifier-free formulas, or semilinear representations. Our results imply that recognizable separability of rational subsets of Σ* × ℕ^d (shown decidable by Choffrut and Grigorieff) is coNP-complete as well. Another application is that regularity of deterministic Parikh automata (where the target set is specified using a quantifier-free Presburger formula) is coNP-complete as well.
Cite as

Elias Rojas Collins, Chris Köcher, and Georg Zetzsche. The Complexity of Separability for Semilinear Sets and Parikh Automata. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{collins_et_al:LIPIcs.MFCS.2025.38,
  author =	{Collins, Elias Rojas and K\"{o}cher, Chris and Zetzsche, Georg},
  title =	{{The Complexity of Separability for Semilinear Sets and Parikh Automata}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{38:1--38:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.38},
  URN =		{urn:nbn:de:0030-drops-241457},
  doi =		{10.4230/LIPIcs.MFCS.2025.38},
  annote =	{Keywords: Vector Addition System, Separability, Regular Language}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.8
Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms

Authors: Cyril Nicaud, Carine Pivoteau, and Stéphane Vialette

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
We investigate the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms from the perspective of computer architecture, focusing on the effects of incorporating a simple branch prediction mechanism into the computational model. Assuming a fixed pattern and a random text, we derive precise estimates for the number of branch mispredictions incurred by these algorithms when using local predictors. Our analysis relies on tools from automata theory and Markov chains, offering a theoretical framework that can be extended to other text processing algorithms and more sophisticated branch prediction strategies.
Cite as

Cyril Nicaud, Carine Pivoteau, and Stéphane Vialette. Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nicaud_et_al:LIPIcs.CPM.2025.8,
  author =	{Nicaud, Cyril and Pivoteau, Carine and Vialette, St\'{e}phane},
  title =	{{Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.8},
  URN =		{urn:nbn:de:0030-drops-231027},
  doi =		{10.4230/LIPIcs.CPM.2025.8},
  annote =	{Keywords: Pattern matching, branch prediction, transducers, average case complexity, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.19
One Drop of Non-Determinism in a Random Deterministic Automaton

Authors: Arnaud Carayol, Philippe Duchon, Florent Koechlin, and Cyril Nicaud

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this article, we investigate this classical result in a probabilistic setting where we take a deterministic automaton with n states uniformly at random and add just one random transition. These automata are almost deterministic in the sense that only one state has a non-deterministic choice when reading an input letter. In our model each state has a fixed probability to be final. We prove that for any d ≥ 1, with non-negligible probability the minimal (deterministic) automaton of the language recognized by such an automaton has more than n^d states; as a byproduct, the expected size of its minimal automaton grows faster than any polynomial. Our result also holds when each state is final with some probability that depends on n, as long as it is not too close to 0 and 1, at distance at least Ω(1/√n) to be precise, therefore allowing models with a sublinear number of final states in expectation.
Cite as

Arnaud Carayol, Philippe Duchon, Florent Koechlin, and Cyril Nicaud. One Drop of Non-Determinism in a Random Deterministic Automaton. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{carayol_et_al:LIPIcs.STACS.2023.19,
  author =	{Carayol, Arnaud and Duchon, Philippe and Koechlin, Florent and Nicaud, Cyril},
  title =	{{One Drop of Non-Determinism in a Random Deterministic Automaton}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.19},
  URN =		{urn:nbn:de:0030-drops-176719},
  doi =		{10.4230/LIPIcs.STACS.2023.19},
  annote =	{Keywords: non-deterministic automaton, powerset construction, probabilistic analysis}
}
Document
DOI: 10.4230/LIPIcs.CPM.2022.13
Back-To-Front Online Lyndon Forest Construction

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

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

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.
Cite as

Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert, and Cyril Nicaud. Back-To-Front Online Lyndon Forest Construction. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{badkobeh_et_al:LIPIcs.CPM.2022.13,
  author =	{Badkobeh, Golnaz and Crochemore, Maxime and Ellert, Jonas and Nicaud, Cyril},
  title =	{{Back-To-Front Online Lyndon Forest Construction}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{13:1--13:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.13},
  URN =		{urn:nbn:de:0030-drops-161404},
  doi =		{10.4230/LIPIcs.CPM.2022.13},
  annote =	{Keywords: Lyndon factorisation, Lyndon forest, Lyndon table, Lyndon array, right Lyndon tree, Cartesian tree, standard factorisation, online algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.48
Absorbing Patterns in BST-Like Expression-Trees

Authors: Florent Koechlin and Pablo Rotondo

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
In this article we study the effect of simple semantic reductions on random BST-like expression-trees. Such random unary-binary expression-trees are often used in benchmarks for model-checking tools. We consider the reduction induced by an absorbing pattern for some given operator ⊛, which we apply bottom-up, producing an equivalent (and smaller) tree-expression. Our main result concerns the expected size of a random tree, of given input size n → ∞, after reduction. We show that there are two different thresholds, leading to a total of five regimes, ranging from no significant reduction at all, to almost complete reduction. These regimes are completely characterized according to the probability of the absorbing operator. Our results prove that random BST-like trees have to be considered with care, and that they offer a richer range of behaviours than uniform random trees.
Cite as

Florent Koechlin and Pablo Rotondo. Absorbing Patterns in BST-Like Expression-Trees. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{koechlin_et_al:LIPIcs.STACS.2021.48,
  author =	{Koechlin, Florent and Rotondo, Pablo},
  title =	{{Absorbing Patterns in BST-Like Expression-Trees}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.48},
  URN =		{urn:nbn:de:0030-drops-136933},
  doi =		{10.4230/LIPIcs.STACS.2021.48},
  annote =	{Keywords: BST trees, absorbing pattern, reduction, analytic combinatorics}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.114
Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Authors: Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series. We first prove a strong version of a conjecture by Castiglione and Massazza: weakly-unambiguous Parikh automata are equivalent to unambiguous two-way reversal bounded counter machines, and their multivariate generating series are holonomic. We then show that the converse is not true: we construct a language whose generating series is algebraic (thus holonomic), but which is inherently weakly-ambiguous as a Parikh automata language. Finally, we prove an effective decidability result for the inclusion problem for weakly-unambiguous Parikh automata, and provide an upper-bound on its complexity.
Cite as

Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 114:1-114:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bostan_et_al:LIPIcs.ICALP.2020.114,
  author =	{Bostan, Alin and Carayol, Arnaud and Koechlin, Florent and Nicaud, Cyril},
  title =	{{Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{114:1--114:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.114},
  URN =		{urn:nbn:de:0030-drops-125212},
  doi =		{10.4230/LIPIcs.ICALP.2020.114},
  annote =	{Keywords: generating series, holonomicity, ambiguity, reversal bounded counter machine, Parikh automata}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.51
Uniform Random Expressions Lack Expressivity

Authors: Florent Koechlin, Cyril Nicaud, and Pablo Rotondo

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this article, we question the relevance of uniform random models for algorithms that use expressions as inputs. Using a general framework to describe expressions, we prove that if there is a subexpression that is absorbing for a given operator, then, after repeatedly applying the induced simplification to a uniform random expression of size n, we obtain an equivalent expression of constant expected size. This proves that uniform random expressions lack expressivity, as soon as there is an absorbing pattern. For instance, (a+b)^* is absorbing for the union for regular expressions on {a,b}, hence random regular expressions can be drastically reduced using the induced simplification.
Cite as

Florent Koechlin, Cyril Nicaud, and Pablo Rotondo. Uniform Random Expressions Lack Expressivity. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{koechlin_et_al:LIPIcs.MFCS.2019.51,
  author =	{Koechlin, Florent and Nicaud, Cyril and Rotondo, Pablo},
  title =	{{Uniform Random Expressions Lack Expressivity}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.51},
  URN =		{urn:nbn:de:0030-drops-109957},
  doi =		{10.4230/LIPIcs.MFCS.2019.51},
  annote =	{Keywords: Random expressions, simplification algorithms, analytic combinatorics}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.40
An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting

Authors: Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R^3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be "lifted" to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations.
Cite as

Xavier Goaoc, Andreas Holmsen, and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2019.40,
  author =	{Goaoc, Xavier and Holmsen, Andreas and Nicaud, Cyril},
  title =	{{An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.40},
  URN =		{urn:nbn:de:0030-drops-104442},
  doi =		{10.4230/LIPIcs.SoCG.2019.40},
  annote =	{Keywords: Geometric permutation, Emptiness testing of semi-algebraic sets, Computer-aided proof}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.4
On the Worst-Case Complexity of TimSort

Authors: Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in O(n log n). The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in O(n + n log rho), where rho is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.
Cite as

Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the Worst-Case Complexity of TimSort. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.ESA.2018.4,
  author =	{Auger, Nicolas and Jug\'{e}, Vincent and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{On the Worst-Case Complexity of TimSort}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.4},
  URN =		{urn:nbn:de:0030-drops-94678},
  doi =		{10.4230/LIPIcs.ESA.2018.4},
  annote =	{Keywords: Sorting algorithms, Merge sorting algorithms, TimSort, Analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.21
Gapped Pattern Statistics

Authors: Philippe Duchon, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
We give a probabilistic analysis of parameters related to alpha-gapped repeats and palindromes in random words, under both uniform and memoryless distributions (where letters have different probabilities, but are drawn independently). More precisely, we study the expected number of maximal alpha-gapped patterns, as well as the expected length of the longest alpha-gapped pattern in a random word.
Cite as

Philippe Duchon, Cyril Nicaud, and Carine Pivoteau. Gapped Pattern Statistics. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{duchon_et_al:LIPIcs.CPM.2017.21,
  author =	{Duchon, Philippe and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{Gapped Pattern Statistics}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.21},
  URN =		{urn:nbn:de:0030-drops-73309},
  doi =		{10.4230/LIPIcs.CPM.2017.21},
  annote =	{Keywords: combinatorics on words, alpha-gapped repeats, random words, memoryless sources, analytic combinatorics}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.43
Fast Synchronization of Random Automata

Authors: Cyril Nicaud

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerny conjectured in 1964 that if a $n$-state deterministic automaton has a synchronizing word, then it has a synchronizing word of length at most (n-1)^2. Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization: he proved that, for the uniform distribution on deterministic automata with n states, an automaton admits a synchronizing word with high probability. In this article, we are interested in the typical length of the smallest synchronizing word, when such a word exists: we prove that a random automaton admits a synchronizing word of length O(n log^{3}n) with high probability. As a consequence, this proves that most automata satisfy the Cerny conjecture.
Cite as

Cyril Nicaud. Fast Synchronization of Random Automata. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 43:1-43:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{nicaud:LIPIcs.APPROX-RANDOM.2016.43,
  author =	{Nicaud, Cyril},
  title =	{{Fast Synchronization of Random Automata}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{43:1--43:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.43},
  URN =		{urn:nbn:de:0030-drops-66665},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.43},
  annote =	{Keywords: random automata, synchronization, the \v{C}ern\'{y} conjecture}
}
Document
DOI: 10.4230/LIPIcs.CPM.2016.9
Estimating Statistics on Words Using Ambiguous Descriptions

Authors: Cyril Nicaud

Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

Abstract
In this article we propose an alternative way to prove some recent results on statistics on words, such as the expected number of runs or the expected sum of the run exponents. Our approach consists in designing a general framework, based on the symbolic method developped in analytic combinatorics. The descriptions obtained in this framework are built in such a way that the degree of ambiguity of an object O (i.e., the number of different descriptions corresponding to O) is exactly the value of the statistic under study for O. The asymptotic estimation of the expectation is then done using classical techniques from analytic combinatorics. To show the generality of our method, we not only apply it to obtain new proofs of known results but also extend them from the uniform distribution to any memoryless distribution.
Cite as

Cyril Nicaud. Estimating Statistics on Words Using Ambiguous Descriptions. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{nicaud:LIPIcs.CPM.2016.9,
  author =	{Nicaud, Cyril},
  title =	{{Estimating Statistics on Words Using Ambiguous Descriptions}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Grossi, Roberto and Lewenstein, Moshe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.9},
  URN =		{urn:nbn:de:0030-drops-60859},
  doi =		{10.4230/LIPIcs.CPM.2016.9},
  annote =	{Keywords: random words, runs, symbolic method, analytic combinatorics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.12
Good Predictions Are Worth a Few Comparisons

Authors: Nicolas Auger, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types.
Cite as

Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good Predictions Are Worth a Few Comparisons. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.STACS.2016.12,
  author =	{Auger, Nicolas and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{Good Predictions Are Worth a Few Comparisons}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.12},
  URN =		{urn:nbn:de:0030-drops-57135},
  doi =		{10.4230/LIPIcs.STACS.2016.12},
  annote =	{Keywords: branch misses, binary search, exponentiation by squaring, Markov chains}
}
  • Refine by Type
  • 18 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2023
  • 1 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 14 Nicaud, Cyril
  • 5 Pivoteau, Carine
  • 4 Koechlin, Florent
  • 3 Carayol, Arnaud
  • 2 Auger, Nicolas
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorics on words
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Regular languages
  • Show More...

  • Refine by Keyword
  • 4 analytic combinatorics
  • 2 Markov chains
  • 2 random words
  • 1 Algorithms with Predictions
  • 1 Analysis of algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact