7 Search Results for "Carayol, Arnaud"


Document
One Drop of Non-Determinism in a Random Deterministic Automaton

Authors: Arnaud Carayol, Philippe Duchon, Florent Koechlin, and Cyril Nicaud

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)


Abstract
Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this article, we investigate this classical result in a probabilistic setting where we take a deterministic automaton with n states uniformly at random and add just one random transition. These automata are almost deterministic in the sense that only one state has a non-deterministic choice when reading an input letter. In our model each state has a fixed probability to be final. We prove that for any d ≥ 1, with non-negligible probability the minimal (deterministic) automaton of the language recognized by such an automaton has more than n^d states; as a byproduct, the expected size of its minimal automaton grows faster than any polynomial. Our result also holds when each state is final with some probability that depends on n, as long as it is not too close to 0 and 1, at distance at least Ω(1/√n) to be precise, therefore allowing models with a sublinear number of final states in expectation.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
Absorbing Patterns in BST-Like Expression-Trees

Authors: Florent Koechlin and Pablo Rotondo

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
In this article we study the effect of simple semantic reductions on random BST-like expression-trees. Such random unary-binary expression-trees are often used in benchmarks for model-checking tools. We consider the reduction induced by an absorbing pattern for some given operator ⊛, which we apply bottom-up, producing an equivalent (and smaller) tree-expression. Our main result concerns the expected size of a random tree, of given input size n → ∞, after reduction. We show that there are two different thresholds, leading to a total of five regimes, ranging from no significant reduction at all, to almost complete reduction. These regimes are completely characterized according to the probability of the absorbing operator. Our results prove that random BST-like trees have to be considered with care, and that they offer a richer range of behaviours than uniform random trees.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Authors: Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series. We first prove a strong version of a conjecture by Castiglione and Massazza: weakly-unambiguous Parikh automata are equivalent to unambiguous two-way reversal bounded counter machines, and their multivariate generating series are holonomic. We then show that the converse is not true: we construct a language whose generating series is algebraic (thus holonomic), but which is inherently weakly-ambiguous as a Parikh automata language. Finally, we prove an effective decidability result for the inclusion problem for weakly-unambiguous Parikh automata, and provide an upper-bound on its complexity.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
Tree Automata with Global Constraints for Infinite Trees

Authors: Patrick Landwehr and Christof Löding

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We study an extension of tree automata on infinite trees with global equality and disequality constraints. These constraints can enforce that all subtrees for which in the accepting run a state q is reached (at the root of that subtree) are identical, or that these trees differ from the subtrees at which a state q' is reached. We consider the closure properties of this model and its decision problems. While the emptiness problem for the general model remains open, we show the decidability of the emptiness problem for the case that the given automaton only uses equality constraints.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
Optimal Strategies in Pushdown Reachability Games

Authors: Arnaud Carayol and Matthew Hague

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
An algorithm for computing optimal strategies in pushdown reachability games was given by Cachat. We show that the information tracked by this algorithm is too coarse and the strategies constructed are not necessarily optimal. We then show that the algorithm can be refined to recover optimality. Through a further non-trivial argument the refined algorithm can be run in 2EXPTIME by bounding the play-lengths tracked to those that are at most doubly exponential. This is optimal in the sense that there exists a game for which the optimal strategy requires a doubly exponential number of moves to reach a target configuration.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
On Long Words Avoiding Zimin Patterns

Authors: Arnaud Carayol and Stefan Göller

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
A pattern is encountered in a word if some infix of the word is the image of the pattern under some non-erasing morphism. A pattern p is unavoidable if, over every finite alphabet, every sufficiently long word encounters p. A theorem by Zimin and independently by Bean, Ehrenfeucht and McNulty states that a pattern over n distinct variables is unavoidable if, and only if, p itself is encountered in the n-th Zimin pattern. Given an alphabet size k, we study the minimal length f(n,k) such that every word of length f(n,k) encounters the n-th Zimin pattern. It is known that f is upper-bounded by a tower of exponentials. Our main result states that f(n,k) is lower-bounded by a tower of n-3 exponentials, even for k=2. To the best of our knowledge, this improves upon a previously best-known doubly-exponential lower bound. As a further result, we prove a doubly-exponential upper bound for encountering Zimin patterns in the abelian sense.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
Document
Distribution of the number of accessible states in a random deterministic automaton

Authors: Arnaud Carayol and Cyril Nicaud

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)


Abstract
We study the distribution of the number of accessible states in deterministic and complete automata with n states over a k-letters alphabet. We show that as n tends to infinity and for a fixed alphabet size, the distribution converges in law toward a Gaussian centered around vk n and of standard deviation equivalent to sk n^(1/2), for some explicit constants vk and sk. Using this characterization, we give a simple algorithm for random uniform generation of accessible deterministic and complete automata of size n of expected complexity O(n^(3/2)), which matches the best methods known so far. Moreover, if we allow a variation around n in the size of the output automaton, our algorithm is the first solution of linear expected complexity. Finally we show how this work can be used to study accessible automata (which are difficult to apprehend from a combinatorial point of view) through the prism of the simpler deterministic and complete automata. As an example, we show how the average complexity in O(n log log n) for Moore's minimization algorithm obtained by David for deterministic and complete automata can be extended to accessible automata.

Cite as

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)


Copy BibTex To Clipboard

@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-dev.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}
}
  • Refine by Author
  • 5 Carayol, Arnaud
  • 3 Koechlin, Florent
  • 3 Nicaud, Cyril
  • 1 Bostan, Alin
  • 1 Duchon, Philippe
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Automata over infinite objects
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Probability and statistics
  • Show More...

  • Refine by Keyword
  • 1 BST trees
  • 1 Context Free
  • 1 Formal Methods
  • 1 Optimal Strategies
  • 1 Parikh automata
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 2012
  • 1 2017
  • 1 2018
  • 1 2019
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail