Cyril Nicaud's homepage

Cyril Nicaud
Laboratoire d'Informatique Gaspard Monge (LIGM)
Université Paris-Est

Main research interests

average case analysis of algorithms,
random generation,
analytic combinatorics

applied to

more realistic models of computation,
classical algorithms,
automata theory, text algorithms
infinite groups

PhD Students

Florent Koechlin 2018 - 2022 (Co-supervisor with A. Carayol), he is now researcher at CNRS
Nicolas Auger 2014 - 2018 (Co-supervisor with C. Pivoteau)
Sven De Felice 2010 - 2014 (Supervisor)
Omar Aït Mous 2008 - 2012 (Co-supervisor with F. Bassino)
Julien David 2007 - 2010 (Co-supervisor with F. Bassino), he is now assistant professor at Unicaen

Publications

Book chapter

Frédérique Bassino, Ilya Kapovich, Markus Lohrey, Alexei Myasnikov, Cyril Nicaud, Andrey Nikolaev, Igor Rivin, Vladimir Shpilrain, Alexander Ushakov and Pascal Weil. Complexity and Randomness in Group Theory. 441 pages. De Gruyter Studium. To appear.

Journals

Frédérique Bassino, Cyril Nicaud, Pascal Weil. Statistics of subgroups of the modular group. Int. J. Algebra Comput. 31(8): 1691-1751 (2021)
Cyril Nicaud, Pablo Rotondo. Random Regular Expression Over Huge Alphabets. Int. J. Found. Comput. Sci. 32(5): 419-438 (2021) [j16]
Florent Koechlin, Cyril Nicaud, Pablo Rotondo. Simplifications of Uniform Expressions Specified by Systems. Int. J. Found. Comput. Sci. 32(6): 733-760 (2021)
Xavier Goaoc, Andreas F. Holmsen, Cyril Nicaud. An experimental study of forbidden patterns in geometric permutations by combinatorial lifting. J. Comput. Geom. 11(2): 131-161 (2020)
Mathilde Bouvel, Marni Mishna and Cyril Nicaud. Some families of trees arising in permutation analysis. Electronic Journal of Combinatorics 27(2): 2 (2020)
Mikhail V. Berlinkov, Cyril Nicaud Synchronizing Almost-Group Automata. Int. J. Found. Comput. Sci. 31(8): 1091-1112 (2020)
Cyril Nicaud. The Cerny Conjecture Holds with High Probability. Journal of Automata, Languages and Combinatorics 24(2-4): 343-365 (2019)
Sven De Felice and Cyril Nicaud. Average case analysis of Brzozowski's algorithm. International Journal of Foundations of Computer Science 27(2): 109-126 (2016)
Frederique Bassino, Cyril Nicaud, and Pascal Weil. Generic properties of subgroups of free groups and of finite presentations. Contemporary Mathematics. Algebra and Computer Science (677): 1–44 (2016)
Frédérique Bassino, Cyril Nicaud, and Pascal Weil. On the genericity of Whitehead minimality. Journal of Group Theory (19): 137–159 (2016)
Otfried Cheong, Xavier Goaoc, and Cyril Nicaud. Set systems and families of permutations with small traces. European Journal of Combinatorics 34 (2): 229-239 (2013)
Frédérique Bassino, Armando Martino, Cyril Nicaud, Enric Ventura, and Pascal Weil. Statistical properties of subgroups of free groups. Random Structures and Algorithms 42(3): 349-373 (2013)
Sarah Behrens, Cyril Nicaud and Pierre Nicodème. An automaton approach for waiting times in DNA evolution. Journal of Computational Biology 19(5): 550-562 (2012)
Frédérique Bassino, Julien David, and Cyril Nicaud. Average Case Analysis of Moore's State Minimization Algorithm. Algorithmica 63 (1): 509-531 (2012)
Pierre-Cyrille Héam, Cyril Nicaud, and Sylvain Schmitz. Parametric Random Generation of Deterministic Tree Automata. Theoretical Computer Science 411(38-39): 3469-3480 (2010)
Frédérique Bassino, Laura Giambruno, and Cyril Nicaud. The average state complexity of rational operations on finite languages. International Journal of Foundations of Computer Science 21(4): 495-516 (2010)
Frédérique Bassino, Julien David, and Cyril Nicaud. Enumeration and random generation of possibly incomplete deterministic automata. Pure Mathematics and Applications 19 (2-3): 1-16 (2009)
Frédérique Bassino, Cyril Nicaud, and Pascal Weil. Random generation of finitely generated subgroups of a free group. International Journal of Algebra and Computation 18(2): 375-405 (2008)
Frédérique Bassino and Cyril Nicaud. Enumeration and Random Generation of Accessible Automata. Theoretical Computer Science 381(1-3): 86-104 (2007)
Frédérique Bassino, Julien Clément, and Cyril Nicaud. The Standard Factorization of Lyndon Words: an Average Point of View. Discrete Mathematics 290(1): 1-25 (2005)

In proceedings

Arnaud Carayol, Philippe Duchon, Florent Koechlin, Cyril Nicaud. One Drop of Non-Determinism in a Random Deterministic Automaton. STACS'23 (14 p.)
Conrado Martínez, Cyril Nicaud, Pablo Rotondo. A Probabilistic Model Revealing Shortcomings in Lua's Hybrid Tables. COCOON'22 (13 p.)
Golnaz Badkobeh, Maxime Crochemore, Jonas Ellert, Cyril Nicaud. Back-To-Front Online Lyndon Forest Construction. CPM'22 (14 p.)
Alin Bostan, Arnaud Carayol, Florent Koechlin and Cyril Nicaud. Weakly-unambiguous Parikh automata and their link to holonomic series ICALP'20 (16 p.)
Florent Koechlin, Cyril Nicaud and Pablo Rotondo. On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations DLT'20 (12 p.)
Florent Koechlin, Cyril Nicaud and Pablo Rotondo. Uniform Random Expressions Lack Expressivity MFCS'19 (14 p.)
Xavier Goaoc, Andreas Holmsen and Cyril Nicaud. An Experimental Study of Forbidden Patterns in Geometric Permutations by Combinatorial Lifting SoCG'19 (16 p.)
Nicolas Auger, Vincent Jugé, Cyril Nicaud and Carine Pivoteau. On the Worst-Case Complexity of TimSort ESA'18 (12 p.)
Philippe Duchon, and Cyril Nicaud. On the Expected Number of Distinct Gapped Palindromic Factors IWOCA'18 (12 p.)
Mikhail Berlinkov, and Cyril Nicaud. Synchronizing Random Almost-Group Automata CIAA'18 (12 p.)
Philippe Duchon, and Cyril Nicaud. On the Biased Partial Word Collector Problem LATIN'18 (14 p.)
Philippe Duchon, Cyril Nicaud, and Carine Pivoteau. Gapped pattern statistics CPM'17 (12 p.)
Cyril Nicaud. Fast Synchronization of Random Automata. RANDOM'16 (12 p.)
Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, and Carine Pivoteau. Analysis of Algorithms for Permutations Biased by Their Number of Records. AofA'16 (12 p.)
Cyril Nicaud. Estimating Statistics on Words Using Ambiguous Descriptions. CPM'16 (11 p.)
Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good predictions are worth a few comparisons. STACS'16 (12 p.)
Cyril Nicaud. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm. CPM'15 (11 p.)
Sven De Felice and Cyril Nicaud. On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States. DLT'14 (12 p.)
Cyril Nicaud. Random Deterministic Automata. MFCS'14 (invited talk + proceedings 19 p.)
Sven De Felice and Cyril Nicaud. Brzozowski algorithm is generically super-polynomial for deterministic automata. DLT'13 (12 p.)
Mathilde Bouvel, Marni Mishna and Cyril Nicaud. Some simple varieties of trees arising in permutation analysis (Extended abstract). FPSAC'13: (poster + proceedings 12 p.)
Sven De Felice and Cyril Nicaud. Random generation of acyclic automata using the recursive method. CSR'13 (12 p.)
Frédérique Bassino, Cyril Nicaud, and Pascal Weil. Generic properties of random subgroups of a free group for general distributions. AofA'12 (12 p.)
Omar Ait Mous, Frédérique Bassino, and Cyril Nicaud. An Efficient Linear Pseudo-Minimization Algorithm for Aho-Corasick Automata CPM'12 (14 p.)
Arnaud Carayol and Cyril Nicaud. Distribution of the number of accessible states in a random deterministic automaton. STACS'12 (12 p.)
Pierre-Cyrille Héam and Cyril Nicaud. Seed, an Easy-to-Use Random Generator of Recursive Data Structures for Testing. ICST'11 (10 p.). The Java software is available here.
Giusi Castiglione, Cyril Nicaud, and Marinella Sciortino. A challenging family of automata for classical minimization algorithms. CIAA'10 (10 p.)
Cyril Nicaud, Carine Pivoteau, and Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. FSTTCS'10 (12 p.)
Omar Ait Mous, Frédérique Bassino, and Cyril Nicaud. Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality. CPM'10 (13 p.)
Frédérique Bassino, Laura Giambruno, and Cyril Nicaud. Complexity of Operations on Cofinite Languages. LATIN'10 (12 p.)
Frédérique Bassino, Armando Martino, Cyril Nicaud, Enric Ventura, and Pascal Weil. On distributions of subgroups of free groups. ANALCO'10 (8 p.)
Dominique Gouyou-Beauchamps and Cyril Nicaud. Random Generation Using Binomial Approximations. AofA'10 (14 p.)
Frédérique Bassino, Julien David, and Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. STACS'09 (12 p.)
Cyril Nicaud. On the average size of Glushkov's automata. LATA'09 (12 p.)
Pierre-Cyrille Héam, Cyril Nicaud, and Sylvain Schmitz. Random Generation of Deterministic Tree (Walking) Automata. CIAA'09 (10 p.)
Frédérique Bassino, Laura Giambruno, and Cyril Nicaud. The average state complexity of the star of a finite set of words is linear. DLT'08 (12 p.)
Frédérique Bassino, Julien David, and Cyril Nicaud. Random generation of possibly incomplete deterministic automata. Gascom'08 (10 p.)
Frédérique Bassino, Julien David, and Cyril Nicaud. REGAL: a library to randomly and exhaustively generate automata. CIAA'07 (poster +proceedings 3 p.)
Frédérique Bassino and Cyril Nicaud. Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers. MathInfo'06 (10 p.)
Frédérique Bassino, Julien Clément, and Cyril Nicaud. Lyndon words with a fixed standard right factor. SODA'04 (short paper 2 p.)
Frédérique Bassino, Julien Clément, and Cyril Nicaud. The average lengths of the factors of the standard factorization of Lyndon words. DLT'02 (12 p.)
Cyril Nicaud. Average State Complexity of Operations on Unary Automata. MFCS'99 (10 p.)