Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Arnaud Carayol and Lucien Charamond. The Structure of Trees in the Pushdown Hierarchy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 131:1-131:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{carayol_et_al:LIPIcs.ICALP.2024.131, author = {Carayol, Arnaud and Charamond, Lucien}, title = {{The Structure of Trees in the Pushdown Hierarchy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {131:1--131:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.131}, URN = {urn:nbn:de:0030-drops-202749}, doi = {10.4230/LIPIcs.ICALP.2024.131}, annote = {Keywords: Pushdown hierarchy, Monadic second-order logic, Automatic numbers} }
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 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 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Patrick Landwehr and Christof Löding. Tree Automata with Global Constraints for Infinite Trees. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{landwehr_et_al:LIPIcs.STACS.2019.47, author = {Landwehr, Patrick and L\"{o}ding, Christof}, title = {{Tree Automata with Global Constraints for Infinite Trees}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {47:1--47:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.47}, URN = {urn:nbn:de:0030-drops-102863}, doi = {10.4230/LIPIcs.STACS.2019.47}, annote = {Keywords: Tree automata, infinite trees, global constraints} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Arnaud Carayol and Matthew Hague. Optimal Strategies in Pushdown Reachability Games. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{carayol_et_al:LIPIcs.MFCS.2018.42, author = {Carayol, Arnaud and Hague, Matthew}, title = {{Optimal Strategies in Pushdown Reachability Games}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {42:1--42:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.42}, URN = {urn:nbn:de:0030-drops-96248}, doi = {10.4230/LIPIcs.MFCS.2018.42}, annote = {Keywords: Pushdown Systems, Reachability Games, Optimal Strategies, Formal Methods, Context Free} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Arnaud Carayol and Stefan Göller. On Long Words Avoiding Zimin Patterns. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{carayol_et_al:LIPIcs.STACS.2017.19, author = {Carayol, Arnaud and G\"{o}ller, Stefan}, title = {{On Long Words Avoiding Zimin Patterns}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.19}, URN = {urn:nbn:de:0030-drops-70140}, doi = {10.4230/LIPIcs.STACS.2017.19}, annote = {Keywords: Unavoidable patterns, combinatorics on words, lower bounds} }
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} }