Resolving Nondeterminism by Chance
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910088792375296 |
|---|---|
| author | Paul, Soumyajit Purser, David Schewe, Sven Tang, Qiyi Totzke, Patrick Yen, Di-De |
| author_facet | Paul, Soumyajit Purser, David Schewe, Sven Tang, Qiyi Totzke, Patrick Yen, Di-De |
| contents | History-deterministic automata are those in which nondeterministic choices can be correctly resolved stepwise: there is a strategy to select a continuation of a run given the next input letter so that if the overall input word admits some accepting run, then the constructed run is also accepting.
Motivated by checking qualitative properties in probabilistic verification, we consider the setting where the resolver strategy can randomize and only needs to succeed with lower-bounded probability. We study the expressiveness of such stochastically-resolvable automata as well as consider the decision questions of whether a given automaton has this property. In particular, we show that it is undecidable to check if a given NFA is $λ$-stochastically resolvable. This problem is decidable for finitely-ambiguous automata. We also present complexity upper and lower bounds for several well-studied classes of automata for which this problem remains decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10234 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Resolving Nondeterminism by Chance Paul, Soumyajit Purser, David Schewe, Sven Tang, Qiyi Totzke, Patrick Yen, Di-De Formal Languages and Automata Theory History-deterministic automata are those in which nondeterministic choices can be correctly resolved stepwise: there is a strategy to select a continuation of a run given the next input letter so that if the overall input word admits some accepting run, then the constructed run is also accepting. Motivated by checking qualitative properties in probabilistic verification, we consider the setting where the resolver strategy can randomize and only needs to succeed with lower-bounded probability. We study the expressiveness of such stochastically-resolvable automata as well as consider the decision questions of whether a given automaton has this property. In particular, we show that it is undecidable to check if a given NFA is $λ$-stochastically resolvable. This problem is decidable for finitely-ambiguous automata. We also present complexity upper and lower bounds for several well-studied classes of automata for which this problem remains decidable. |
| title | Resolving Nondeterminism by Chance |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2504.10234 |