Cyril Nicaud
68
Documents
Publications
Simplifications of Uniform Expressions Specified by SystemsInternational Journal of Foundations of Computer Science, 2021, 32 (06), pp.733-760. ⟨10.1142/S0129054121420065⟩
Article dans une revue
hal-04484336v1
|
|
Random Regular Expression Over Huge AlphabetsInternational Journal of Foundations of Computer Science, 2021, 32 (05), pp.419-438. ⟨10.1142/S012905412141001X⟩
Article dans une revue
hal-04484425v1
|
|
An experimental study of forbidden patterns in geometric permutations by combinatorial liftingJournal 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
|
|
Simplifications of Uniform Expressions Specified by SystemsInternational Journal of Foundations of Computer Science, 2020, 32 (6), pp.733-760
Article dans une revue
hal-04315975v1
|
|
Some families of trees arising in permutation analysisThe Electronic Journal of Combinatorics, 2020, ⟨10.37236/6504⟩
Article dans une revue
hal-03002214v1
|
|
Synchronizing Almost-Group AutomataInternational Journal of Foundations of Computer Science, 2020, 31 (08), pp.1091-1112. ⟨10.1142/S0129054120420058⟩
Article dans une revue
hal-03134003v1
|
|
The Černý Conjecture Holds with High ProbabilityJournal of Automata Languages and Combinatorics, 2019, 24 (2-4), pp.343-365. ⟨10.25596/jalc-2019-343⟩
Article dans une revue
hal-04315981v1
|
|
|
Average Case Analysis of Brzozowski's AlgorithmInternational Journal of Foundations of Computer Science, 2016, 27 (02), pp.109-126. ⟨10.1142/S0129054116400025⟩
Article dans une revue
hal-01772820v1
|
|
On the genericity of Whitehead minimalityJournal of Group Theory, 2016, 19 (1), pp.137-159
Article dans une revue
hal-00919489v2
|
|
Statistical properties of subgroups of free groupsRandom Structures and Algorithms, 2013, 42, pp.349-373. ⟨10.1002/rsa.20407⟩
Article dans une revue
hal-00450218v3
|
|
Set Systems and Families of Permutations with Small TracesEuropean Journal of Combinatorics, 2013, 34, pp.229-239
Article dans une revue
hal-00752064v1
|
|
Average Case Analysis of Moore's State Minimization Algorithm.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 EvolutionJournal of Computational Biology, 2012, 19 (5), pp.550-562. ⟨10.1089/cmb.2011.0218⟩
Article dans une revue
hal-00793413v1
|
|
|
The Average State Complexity of Rational Operations on Finite LanguagesInternational Journal of Foundations of Computer Science, 2010, 21 (4), pp.495-515
Article dans une revue
hal-00452751v2
|
|
Parametric Random Generation of Deterministic Tree AutomataTheoretical Computer Science, 2010, 411 (1), pp.3469--3480. ⟨10.1016/j.tcs.2010.05.036⟩
Article dans une revue
hal-00561274v1
|
|
Random generation of finitely generated subgroups of a free groupInternational Journal of Algebra and Computation, 2008, 18 (1), pp.375-405. ⟨10.1142/S0218196708004482⟩
Article dans une revue
hal-00164584v1
|
|
Enumeration and random generation of possibly incomplete deterministic automata.Pure Mathematics and Applications, 2008, 19 (2-3), pp.1-16
Article dans une revue
hal-00452748v1
|
|
Enumeration and random generation of accessible automataTheoretical Computer Science, 2007, 381, pp.86-104
Article dans une revue
hal-00459712v1
|
|
The Standard Factorization of Lyndon Words: an Average Point of ViewDiscrete 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 AutomatonSTACS: Symposium on Theoretical Aspects of Computer Science, 2023, Hamburg, Germany. pp.19:1--19:14, ⟨10.4230/LIPIcs.STACS.2023.1910.4230/LIPIcs.STACS.2023.19⟩
Communication dans un congrès
hal-04316025v1
|
|
|
A Probabilistic Model Revealing Shortcomings in Lua’s Hybrid TablesThe 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
|
A Probabilistic Model Revealing Shortcomings in Lua's Hybrid TablesThe 28th International Computing and Combinatorics Conference, 2022, Shenzhen, China. pp.381-393
Communication dans un congrès
hal-04316043v1
|
|
Back-To-Front Online Lyndon Forest Construction33rd Annual Symposium on Combinatorial Pattern Matching, 2022, Prague, Czech Republic. pp.13:1--13:23
Communication dans un congrès
hal-04316084v1
|
|
|
Weakly-unambiguous Parikh automata and their link to holonomic seriesICALP 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
|
|
On the Degeneracy of Random Expressions Specified by Systems of Combinatorial EquationsInternational 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
|
|
Uniform Random Expressions Lack ExpressivityMFCS 2019, Aug 2019, Aachen, Germany. pp.51:1-51:14, ⟨10.4230/LIPIcs.MFCS.2019.51⟩
Communication dans un congrès
hal-03145930v1
|
An experimental study of forbidden patterns in geometric permutations by combinatorial lifting35th International Symposium on Computational Geometry, 2019, Portland, United States. ⟨10.4230/LIPIcs.SoCG.2019.40⟩
Communication dans un congrès
hal-02050539v1
|
|
On the Expected Number of Distinct Gapped Palindromic FactorsIWOCA 2018: International Workshop on Combinatorial Algorithms, Jul 2018, Singapour, Singapore
Communication dans un congrès
hal-01798294v1
|
|
|
On the Worst-Case Complexity of TimSort26th 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
|
Synchronizing Random Almost-Group Automata23rd 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 ProblemLATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Apr 2018, Buenos Aires, Argentina
Communication dans un congrès
hal-01798293v1
|
|
|
Gapped Pattern Statistics28th 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
|
|
Fast Synchronization of Random AutomataAPPROX/RANDOM 2016, Sep 2016, Paris, France. pp.43.1-12, ⟨10.4230/LIPIcs.APPROX-RANDOM.2016.43⟩
Communication dans un congrès
hal-01719171v1
|
|
Estimating Statistics on Words Using Ambiguous Descriptions27th 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
|
|
Good predictions are worth a few comparisonsSTACS 2016, Feb 2016, Orléans, France. pp.12:1-12:14, ⟨10.4230/LIPIcs.STACS.2016.12⟩
Communication dans un congrès
hal-01212840v1
|
|
Analysis of Algorithms for Permutations Biased by Their Number of Records27th 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
|
|
A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-AlgorithmCPM 2015, Jun 2015, Ischia Island, Italy. pp.374-384, ⟨10.1007/978-3-319-19929-0_32⟩
Communication dans un congrès
hal-01719172v1
|
|
Random Deterministic AutomataMFCS 2014, Aug 2014, Budapest, Hungary. pp.5-23, ⟨10.1007/978-3-662-44522-8_2⟩
Communication dans un congrès
hal-01772890v1
|
|
On the Average Complexity of Brzozowski's Algorithm for Deterministic Automata with a Small Number of Final StatesDLT 2014, Aug 2014, Ekaterinburg, Russia. pp.25-36, ⟨10.1007/978-3-319-09698-8_3⟩
Communication dans un congrès
hal-01772856v1
|
|
Random Generation of Deterministic Acyclic Automata Using the Recursive Method8th 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
|
|
Some simple varieties of trees arising in permutation analysis25th 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
|
|
Brzozowski Algorithm Is Generically Super-Polynomial Deterministic AutomataDLT'13, 2013, France. pp.179-190, ⟨10.1007/978-3-642-38771-5_17⟩
Communication dans un congrès
hal-00841848v1
|
|
Generic properties of random subgroups of a free group for general distributions23rd 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
|
|
Distribution of the number of accessible states in a random deterministic automatonSTACS'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 Automata23st 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 Testing4th 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
|
|
|
Average Analysis of Glushkov Automata under a BST-Like Model30th Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10), 2010, India. pp.388-399
Communication dans un congrès
hal-00620382v1
|
|
On two distributions of subgroups of free groupsWorkshop on Analytic Algorithmics and Combinatorics (ANALCO) 2010, Jan 2010, United States. pp.82-89
Communication dans un congrès
hal-00433210v2
|
A challenging family of automata for classical minimization algorithms15th International Conference on Implementation and Application of Automata (CIAA'10), 2010, Canada. pp.251-260
Communication dans un congrès
hal-00620381v1
|
|
Set Systems and Families of Permutations with Small Traces (abstract)8th French Combinatorial Conference, 2010, France
Communication dans un congrès
hal-00620460v1
|
|
|
Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Jun 2010, United States. pp.275-287
Communication dans un congrès
hal-00450674v2
|
|
Complexity of operations on cofinite languages9th Latin American Theoretical INformatics Symposium (LATIN 2010), Apr 2010, Oaxaca, Mexico. pp.222-233
Communication dans un congrès
hal-00459651v1
|
|
Random Generation Using Binomial Approximations21st 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
|
|
Random Generation of Deterministic Tree (Walking) Automata14th 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
|
|
On the Average Size of Glushkov's Automata3rd 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
|
|
On the Average Complexity of Moore's State Minimization Algorithm26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.123-134
Communication dans un congrès
inria-00359162v1
|
|
The average state complexity of the star of a finite set of words is linear.International Conference on Developments in Language Theory, 2008, Japan. pp.134-145
Communication dans un congrès
hal-00452752v1
|
|
Random generation of possibly incomplete deterministic automata.Génération Aléatoire de Structures COMbinatoires, 2008, Italy. pp.31-40
Communication dans un congrès
hal-00452754v1
|
|
REGAL: a library to randomly and exhaustively generate automata12th 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
|
|
Accessible and Deterministic Automata: Enumeration and Boltzmann SamplersFourth 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
|
|
Lyndon words with a fixed standard right factor15th 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
|
|
The average lengths of the factors of the standard factorization of Lyndon words6th 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 AutomataMFCS 1999, Sep 1999, Szklarska Poreba, Poland, Poland. pp.231-240, ⟨10.1007/3-540-48340-3_21⟩
Communication dans un congrès
hal-00620109v1
|
|
Random presentations and random subgroups: a surveyFré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
|
|
Generic properties of subgroups of free groups and finite presentationsDelaram 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
|
|
Merge Strategies: from Merge Sort to TimSort2015
Pré-publication, Document de travail
hal-01212839v2
|
|
Seed: an easy to use random generator of recursive data structures for testing[Research Report] ENS Cachan. 2009, pp.18
Rapport
inria-00528585v1
|
|
Set Systems and Families of Permutations with Small Traces[Research Report] RR-7154, INRIA. 2009, pp.14
Rapport
inria-00441376v2
|