License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.19
URN: urn:nbn:de:0030-drops-176719
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17671/
Carayol, Arnaud ;
Duchon, Philippe ;
Koechlin, Florent ;
Nicaud, Cyril
One Drop of Non-Determinism in a Random Deterministic Automaton
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.
BibTeX - Entry
@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/opus/volltexte/2023/17671},
URN = {urn:nbn:de:0030-drops-176719},
doi = {10.4230/LIPIcs.STACS.2023.19},
annote = {Keywords: non-deterministic automaton, powerset construction, probabilistic analysis}
}
|
Keywords: |
|
non-deterministic automaton, powerset construction, probabilistic analysis |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
