Accéder directement au contenu

Cyril Nicaud

69
Documents

Publications

Random Regular Expression Over Huge Alphabets

Cyril Nicaud , Pablo Rotondo
International Journal of Foundations of Computer Science, 2021, 32 (05), pp.419-438. ⟨10.1142/S012905412141001X⟩
Article dans une revue hal-04484425v1

Random Regular Expression Over Huge Alphabets

Cyril Nicaud , Pablo Rotondo
International Journal of Foundations of Computer Science, 2021, 32 (5), pp.419-438
Article dans une revue hal-04315964v1

Simplifications of Uniform Expressions Specified by Systems

Florent Koechlin , Cyril Nicaud , Pablo Rotondo
International Journal of Foundations of Computer Science, 2021, 32 (06), pp.733-760. ⟨10.1142/S0129054121420065⟩
Article dans une revue hal-04484336v1

An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

Xavier Goaoc , Andreas Holmsen , Cyril Nicaud
Journal of Computational Geometry, 2021, Special Issue of Selected Papers from SoCG 2019, 11 (2), pp.131-161. ⟨10.20382/jocg.v11i2a6⟩
Article dans une revue hal-03152958v1

Some families of trees arising in permutation analysis

Mathilde Bouvel , Marni Mishna , Cyril Nicaud
The Electronic Journal of Combinatorics, 2020, ⟨10.37236/6504⟩
Article dans une revue hal-03002214v1

Synchronizing Almost-Group Automata

Mikhail Berlinkov , Cyril Nicaud
International Journal of Foundations of Computer Science, 2020, 31 (08), pp.1091-1112. ⟨10.1142/S0129054120420058⟩
Article dans une revue hal-03134003v1

Simplifications of Uniform Expressions Specified by Systems

Florent Koechlin , Cyril Nicaud , Pablo Rotondo
International Journal of Foundations of Computer Science, 2020, 32 (6), pp.733-760
Article dans une revue hal-04315975v1

The Černý Conjecture Holds with High Probability

Cyril Nicaud
Journal of Automata Languages and Combinatorics, 2019, 24 (2-4), pp.343-365. ⟨10.25596/jalc-2019-343⟩
Article dans une revue hal-04315981v1
Image document

On the genericity of Whitehead minimality

Frédérique Bassino , Cyril Nicaud , Pascal Weil
Journal of Group Theory, 2016, 19 (1), pp.137-159
Article dans une revue hal-00919489v2
Image document

Average Case Analysis of Brzozowski's Algorithm

Sven de Felice , Cyril Nicaud
International Journal of Foundations of Computer Science, 2016, 27 (02), pp.109-126. ⟨10.1142/S0129054116400025⟩
Article dans une revue hal-01772820v1
Image document

Statistical properties of subgroups of free groups

Frédérique Bassino , Armando Martino , Cyril Nicaud , Enric Ventura , Pascal Weil
Random Structures and Algorithms, 2013, 42, pp.349-373. ⟨10.1002/rsa.20407⟩
Article dans une revue hal-00450218v3
Image document

Set Systems and Families of Permutations with Small Traces

Otfried Cheong , Xavier Goaoc , Cyril Nicaud
European Journal of Combinatorics, 2013, 34, pp.229-239
Article dans une revue hal-00752064v1
Image document

Average Case Analysis of Moore's State Minimization Algorithm.

Frédérique Bassino , Julien David , Cyril Nicaud
Algorithmica, 2012, 63 (1-2), pp.509-531. ⟨10.1007/s00453-011-9557-7⟩
Article dans une revue hal-00452749v1

An Automaton Approach for Waiting Times in DNA Evolution

Sarah Behrens , Cyril Nicaud , Pierre Nicodème
Journal of Computational Biology, 2012, 19 (5), pp.550-562. ⟨10.1089/cmb.2011.0218⟩
Article dans une revue hal-00793413v1
Image document

The Average State Complexity of Rational Operations on Finite Languages

Frédérique Bassino , Laura Giambruno , Cyril Nicaud
International Journal of Foundations of Computer Science, 2010, 21 (4), pp.495-515
Article dans une revue hal-00452751v2
Image document

Parametric Random Generation of Deterministic Tree Automata

Pierre-Cyrille Heam , Cyril Nicaud , Sylvain Schmitz
Theoretical Computer Science, 2010, 411 (1), pp.3469--3480. ⟨10.1016/j.tcs.2010.05.036⟩
Article dans une revue hal-00561274v1
Image document

Random generation of finitely generated subgroups of a free group

Frédérique Bassino , Cyril Nicaud , Pascal Weil
International Journal of Algebra and Computation, 2008, 18 (1), pp.375-405
Article dans une revue hal-00164584v1
Image document

Enumeration and random generation of possibly incomplete deterministic automata.

Frédérique Bassino , Julien David , Cyril Nicaud
Pure Mathematics and Applications, 2008, 19 (2-3), pp.1-16
Article dans une revue hal-00452748v1
Image document

Enumeration and random generation of accessible automata

Frédérique Bassino , Cyril Nicaud
Theoretical Computer Science, 2007, 381, pp.86-104
Article dans une revue hal-00459712v1
Image document

The Standard Factorization of Lyndon Words: an Average Point of View

Frédérique Bassino , Julien Clément , Cyril Nicaud
Discrete Mathematics, 2005, 290 (1), pp.1-25. ⟨10.1016/j.disc.2004.11.002⟩
Article dans une revue hal-00619337v1

One Drop of Non-Determinism in a Random Deterministic Automaton

Arnaud Carayol , Philippe Duchon , Florent Koechlin , Cyril Nicaud
STACS: Symposium on Theoretical Aspects of Computer Science, 2023, Hamburg, Germany. pp.19:1--19:14
Communication dans un congrès hal-04316025v1

A Probabilistic Model Revealing Shortcomings in Lua's Hybrid Tables

Conrado Martínez , Cyril Nicaud , Pablo Rotondo
The 28th International Computing and Combinatorics Conference, 2022, Shenzhen, China. pp.381-393
Communication dans un congrès hal-04316043v1
Image document

A Probabilistic Model Revealing Shortcomings in Lua’s Hybrid Tables

Conrado Martínez , Cyril Nicaud , Pablo Rotondo
The 28th International Computing and Combinatorics Conference COCOON 2022, Oct 2022, Shenzhen, China. pp.381-393, ⟨10.1007/978-3-031-22105-7_34⟩
Communication dans un congrès hal-04484318v1

Back-To-Front Online Lyndon Forest Construction

Golnaz Badkobeh , Maxime Crochemore , Jonas Ellert , Cyril Nicaud
33rd Annual Symposium on Combinatorial Pattern Matching, 2022, Prague, Czech Republic. pp.13:1--13:23
Communication dans un congrès hal-04316084v1
Image document

Weakly-unambiguous Parikh automata and their link to holonomic series

Alin Bostan , Arnaud Carayol , Florent Koechlin , Cyril Nicaud
ICALP 2020 - 47th International Colloquium on Automata, Languages and Programming, Jul 2020, Saarbrücken, Germany. pp.114.1-114.16, ⟨10.4230/LIPIcs.ICALP.2020.114⟩
Communication dans un congrès hal-03084639v1
Image document

On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations

Florent Koechlin , Cyril Nicaud , Pablo Rotondo
International Conference on Developments in Language Theory (DLT 2020), May 2020, Tampa, United States. pp.164-177, ⟨10.1007/978-3-030-48516-0_13⟩
Communication dans un congrès hal-03145943v1

An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

Xavier Goaoc , Andreas Holmsen , Cyril Nicaud
35th International Symposium on Computational Geometry, 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.40⟩
Communication dans un congrès hal-02050539v1
Image document

Uniform Random Expressions Lack Expressivity

Florent Koechlin , Cyril Nicaud , Pablo Rotondo
MFCS 2019, Aug 2019, Aachen, Germany. pp.51:1-51:14, ⟨10.4230/LIPIcs.MFCS.2019.51⟩
Communication dans un congrès hal-03145930v1

Synchronizing Random Almost-Group Automata

Mikhail V. Berlinkov , Cyril Nicaud
23rd International Conference on Implementation and Application of Automata, 2018, Charlottetown, Canada. pp.84-96
Communication dans un congrès hal-04316115v1

On the Biased Partial Word Collector Problem

Philippe Duchon , Cyril Nicaud
LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Apr 2018, Buenos Aires, Argentina
Communication dans un congrès hal-01798293v1
Image document

On the Worst-Case Complexity of TimSort

Nicolas Auger , Vincent Jugé , Cyril Nicaud , Carine Pivoteau
26th Annual European Symposium on Algorithms (ESA 2018), Aug 2018, Helsinki, Finland. pp.4:1--4:13, ⟨10.4230/LIPIcs.ESA.2018.4⟩
Communication dans un congrès hal-01798381v1

On the Expected Number of Distinct Gapped Palindromic Factors

Philippe Duchon , Cyril Nicaud
IWOCA 2018: International Workshop on Combinatorial Algorithms, Jul 2018, Singapour, Singapore
Communication dans un congrès hal-01798294v1
Image document

Gapped Pattern Statistics

Philippe Duchon , Cyril Nicaud , Carine Pivoteau
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Jul 2017, Varsovie, Poland. pp.21:1-21:12, ⟨10.4230/LIPIcs.CPM.2017.21⟩
Communication dans un congrès hal-01565941v1
Image document

Estimating Statistics on Words Using Ambiguous Descriptions

Cyril Nicaud
27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), Jun 2016, Tel Aviv, Israel. pp.9, ⟨10.4230/LIPIcs.CPM.2016.9⟩
Communication dans un congrès hal-01769095v1
Image document

Fast Synchronization of Random Automata

Cyril Nicaud
APPROX/RANDOM 2016, Sep 2016, Paris, France. pp.43.1-12, ⟨10.4230/LIPIcs.APPROX-RANDOM.2016.43⟩
Communication dans un congrès hal-01719171v1
Image document

Good predictions are worth a few comparisons

Nicolas Auger , Cyril Nicaud , Carine Pivoteau
STACS 2016, Feb 2016, Orléans, France. pp.12:1-12:14, ⟨10.4230/LIPIcs.STACS.2016.12⟩
Communication dans un congrès hal-01212840v1
Image document

Analysis of Algorithms for Permutations Biased by Their Number of Records

Nicolas Auger , Mathilde Bouvel , Cyril Nicaud , Carine Pivoteau
27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithm AOFA 2016, Jul 2016, Cracovie, Poland
Communication dans un congrès hal-01838692v1
Image document

A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm

Cyril Nicaud
CPM 2015, Jun 2015, Ischia Island, Italy. pp.374-384, ⟨10.1007/978-3-319-19929-0_32⟩
Communication dans un congrès hal-01719172v1
Image document

Random Deterministic Automata

Cyril Nicaud
MFCS 2014, Aug 2014, Budapest, Hungary. pp.5-23, ⟨10.1007/978-3-662-44522-8_2⟩
Communication dans un congrès hal-01772890v1
Image document

On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final States

Sven de Felice , Cyril Nicaud
DLT 2014, Aug 2014, Ekaterinburg, Russia. pp.25-36, ⟨10.1007/978-3-319-09698-8_3⟩
Communication dans un congrès hal-01772856v1
Image document

Brzozowski Algorithm Is Generically Super-Polynomial Deterministic Automata

Sven de Felice , Cyril Nicaud
DLT'13, 2013, France. pp.179-190, ⟨10.1007/978-3-642-38771-5_17⟩
Communication dans un congrès hal-00841848v1
Image document

Some simple varieties of trees arising in permutation analysis

Mathilde Bouvel , Marni Mishna , Cyril Nicaud
25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.825-836, ⟨10.46298/dmtcs.2346⟩
Communication dans un congrès hal-01229665v1
Image document

Random Generation of Deterministic Acyclic Automata Using the Recursive Method

Sven de Felice , Cyril Nicaud
8th International Computer Science Symposium in Russia (CSR'13), 2013, Russia. pp.88-99, ⟨10.1007/978-3-642-38536-0_8⟩
Communication dans un congrès hal-00841835v1
Image document

Generic properties of random subgroups of a free group for general distributions

Frédérique Bassino , Cyril Nicaud , Pascal Weil
23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'12), 2012, Canada. pp.155-166, ⟨10.46298/dmtcs.2991⟩
Communication dans un congrès hal-00687981v1
Image document

Distribution of the number of accessible states in a random deterministic automaton

Arnaud Carayol , Cyril Nicaud
STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), Feb 2012, Paris, France. pp.194-205
Communication dans un congrès hal-00678213v1

An Efficient Linear Pseudo-Minimization Algorithm for Aho-Corasick Automata

Omar Aitmous , Frédérique Bassino , Cyril Nicaud
23st Annual Symposium on Combinatorial Pattern Matching (CPM'12), 2012, Finland. pp.110-123
Communication dans un congrès hal-00793395v1

Seed, an Easy-to-Use Random Generator of Recursive Data Structures for Testing

Pierre-Cyrille Héam , Cyril Nicaud
4th IEEE International Conference on Software Testing, Verification and Validation (ICST'11), Mar 2011, Berlin, Germany. pp.60 - 69, ⟨10.1109/ICST.2011.31⟩
Communication dans un congrès hal-00620373v1
Image document

Complexity of operations on cofinite languages

Frédérique Bassino , Laura Giambruno , Cyril Nicaud
9th Latin American Theoretical INformatics Symposium (LATIN 2010), Apr 2010, Oaxaca, Mexico. pp.222-233
Communication dans un congrès hal-00459651v1

A challenging family of automata for classical minimization algorithms

Giusi Castiglione , Cyril Nicaud , Marinella Sciortino
15th International Conference on Implementation and Application of Automata (CIAA'10), 2010, Canada. pp.251-260
Communication dans un congrès hal-00620381v1
Image document

Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality

Omar Aitmous , Frédérique Bassino , Cyril Nicaud
21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Jun 2010, United States. pp.275-287
Communication dans un congrès hal-00450674v2

Set Systems and Families of Permutations with Small Traces (abstract)

Otfried Cheong , Xavier Goaoc , Cyril Nicaud
8th French Combinatorial Conference, 2010, France
Communication dans un congrès hal-00620460v1
Image document

Random Generation Using Binomial Approximations

Dominique Gouyou-Beauchamps , Cyril Nicaud
21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.359-372, ⟨10.46298/dmtcs.2772⟩
Communication dans un congrès hal-01185570v1
Image document

Average Analysis of Glushkov Automata under a BST-Like Model

Cyril Nicaud , Carine Pivoteau , Benoît Razet
30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10), 2010, India. pp.388-399
Communication dans un congrès hal-00620382v1
Image document

On two distributions of subgroups of free groups

Frédérique Bassino , Armando Martino , Cyril Nicaud , Enric Ventura , Pascal Weil
Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 2010, Jan 2010, United States. pp.82-89
Communication dans un congrès hal-00433210v2
Image document

Random Generation of Deterministic Tree (Walking) Automata

Pierre-Cyrille Héam , Cyril Nicaud , Sylvain Schmitz
14th International Conference on Implementation and Application of Automata - CIAA 2009, Jul 2009, Sydney, Australia. pp.115--124, ⟨10.1007/978-3-642-02979-0_15⟩
Communication dans un congrès inria-00408316v1
Image document

On the Average Size of Glushkov's Automata

Cyril Nicaud
3rd International Conference on Language and Automata Theory and Applications (LATA 2009), Apr 2009, Tarragona, Spain. pp.626-637, ⟨10.1007/978-3-642-00982-2_53⟩
Communication dans un congrès hal-00430482v1
Image document

On the Average Complexity of Moore's State Minimization Algorithm

Frédérique Bassino , Julien David , Cyril Nicaud
26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.123-134
Communication dans un congrès inria-00359162v1
Image document

The average state complexity of the star of a finite set of words is linear.

Frédérique Bassino , Laura Giambruno , Cyril Nicaud
International Conference on Developments in Language Theory, 2008, Japan. pp.134-145
Communication dans un congrès hal-00452752v1
Image document

Random generation of possibly incomplete deterministic automata.

Frédérique Bassino , Julien David , Cyril Nicaud
Génération Aléatoire de Structures COMbinatoires, 2008, Italy. pp.31-40
Communication dans un congrès hal-00452754v1
Image document

REGAL: a library to randomly and exhaustively generate automata

Frédérique Bassino , Julien David , Cyril Nicaud
12th International Conference on Implementation and Application of Automata (CIAA'07), Jul 2007, Prague, Czech Republic. pp.303-305., ⟨10.1007/978-3-540-76336-9_28⟩
Communication dans un congrès hal-00459643v1
Image document

Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers

Frédérique Bassino , Cyril Nicaud
Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.151-160, ⟨10.46298/dmtcs.3499⟩
Communication dans un congrès hal-00619870v2
Image document

Lyndon words with a fixed standard right factor

Frédérique Bassino , Julien Clément , Cyril Nicaud
15th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2004), Jan 2004, New Orleans, Louisiana, United States. pp.646-647
Communication dans un congrès hal-00619866v1
Image document

The average lengths of the factors of the standard factorization of Lyndon words

Frédérique Bassino , Julien Clément , Cyril Nicaud
6th International Conference on Developments in Language Theory (DLT 2002), Sep 2003, Kyoto, Japan. pp.307-318
Communication dans un congrès hal-00619865v1

Average State Complexity of Operations on Unary Automata

Cyril Nicaud
MFCS 1999, Sep 1999, Szklarska Poreba, Poland, Poland. pp.231-240, ⟨10.1007/3-540-48340-3_21⟩
Communication dans un congrès hal-00620109v1
Image document

Random presentations and random subgroups: a survey

Frédérique Bassino , Cyril Nicaud , Pascal Weil
Frédérique Bassino, Ilya Kapovich, Markus Lohrey, Alexei Miasnikov, Cyril Nicaud, Andrey Nikolaev, Igor Rivin, Vladimir Shpilrain, Alexander Ushakov and Pascal Weil. Complexity and Randomness in Group Theory - GAGTA Book 1, de Gruyter, 2020, 978-3-11-066491-1
Chapitre d'ouvrage hal-01456207v2
Image document

Generic properties of subgroups of free groups and finite presentations

Frédérique Bassino , Cyril Nicaud , Pascal Weil
Delaram Kahrobaei, Bren Cavallo, David Garber. Algebra and Computer Science, 677, American Mathematical Society, pp.1-44, 2016, Contemporary Mathematics, 978-1-4704-2303-2
Chapitre d'ouvrage hal-01171484v2