5 Search Results for "Koechlin, Florent"

Document
DOI: 10.4230/LIPIcs.STACS.2023.19
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
DOI: 10.4230/LIPIcs.FSTTCS.2022.41
New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages

Authors: Florent Koechlin

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
This article extends the work of Flajolet [Philippe Flajolet, 1987] on the relation between generating series and inherent ambiguity. We first propose an analytic criterion to prove the infinite inherent ambiguity of some context-free languages, and apply it to give a purely combinatorial proof of the infinite ambiguity of Shamir’s language. Then we show how Ginsburg and Ullian’s criterion on unambiguous bounded languages translates into a useful criterion on generating series, which generalises and simplifies the proof of the recent criterion of Makarov [Vladislav Makarov, 2021]. We then propose a new criterion based on generating series to prove the inherent ambiguity of languages with interlacing patterns, like {a^nb^ma^pb^q | n≠p or m≠q, with n,m,p,q ∈ ℕ^*}. We illustrate the applicability of these two criteria on many examples.
Cite as

Florent Koechlin. New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koechlin:LIPIcs.FSTTCS.2022.41,
  author =	{Koechlin, Florent},
  title =	{{New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.41},
  URN =		{urn:nbn:de:0030-drops-174331},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.41},
  annote =	{Keywords: Inherent ambiguity, Infinite ambiguity, Ambiguity, Generating series, Context-free languages, Bounded languages}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.48
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
DOI: 10.4230/LIPIcs.ICALP.2020.114
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
DOI: 10.4230/LIPIcs.MFCS.2019.51
Uniform Random Expressions Lack Expressivity

Authors: Florent Koechlin, Cyril Nicaud, and Pablo Rotondo

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In this article, we question the relevance of uniform random models for algorithms that use expressions as inputs. Using a general framework to describe expressions, we prove that if there is a subexpression that is absorbing for a given operator, then, after repeatedly applying the induced simplification to a uniform random expression of size n, we obtain an equivalent expression of constant expected size. This proves that uniform random expressions lack expressivity, as soon as there is an absorbing pattern. For instance, (a+b)^* is absorbing for the union for regular expressions on {a,b}, hence random regular expressions can be drastically reduced using the induced simplification.
Cite as

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)

Copy BibTex To Clipboard

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

  • Refine by Classification
  • 2 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 2 analytic combinatorics
  • 1 Ambiguity
  • 1 BST trees
  • 1 Bounded languages
  • 1 Context-free languages
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2021
  • 1 2022
  • 1 2023

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact