Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
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)
@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} }
Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
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)
@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} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
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)
@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} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
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)
@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} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
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)
@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} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
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)
@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} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
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)
@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} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
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)
@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} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
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)
@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} }
Published in: LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
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)
@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} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
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)
@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} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Arnaud Carayol and Cyril Nicaud. Distribution of the number of accessible states in a random deterministic automaton. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 194-205, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{carayol_et_al:LIPIcs.STACS.2012.194, author = {Carayol, Arnaud and Nicaud, Cyril}, title = {{Distribution of the number of accessible states in a random deterministic automaton}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {194--205}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.194}, URN = {urn:nbn:de:0030-drops-34422}, doi = {10.4230/LIPIcs.STACS.2012.194}, annote = {Keywords: finite automata, random sampling, average complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Cyril Nicaud, Carine Pivoteau, and Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 388-399, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{nicaud_et_al:LIPIcs.FSTTCS.2010.388, author = {Nicaud, Cyril and Pivoteau, Carine and Razet, Beno\^{i}t}, title = {{Average Analysis of Glushkov Automata under a BST-Like Model}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {388--399}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.388}, URN = {urn:nbn:de:0030-drops-28809}, doi = {10.4230/LIPIcs.FSTTCS.2010.388}, annote = {Keywords: Glushkov automata, random binary search tree, regular expression} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Frederique Bassino, Julien David, and Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 123-134, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{bassino_et_al:LIPIcs.STACS.2009.1822, author = {Bassino, Frederique and David, Julien and Nicaud, Cyril}, title = {{On the Average Complexity of Moore's State Minimization Algorithm}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {123--134}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1822}, URN = {urn:nbn:de:0030-drops-18222}, doi = {10.4230/LIPIcs.STACS.2009.1822}, annote = {Keywords: Finite automata, State minimization, Moore’s algorithm, Average complexity} }
Feedback for Dagstuhl Publishing