2026-07-21T21:12:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23982 2025-11-12T13:25:14Z ddc:004 open_access

Resolving Nondeterminism by Chance Paul, Soumyajit Purser, David Schewe, Sven Tang, Qiyi Totzke, Patrick Yen, Di-De History-determinism finite automata probabilistic automata 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 randomise 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soumyajit Paul and David Purser and Sven Schewe and Qiyi Tang and Patrick Totzke and Di-De Yen 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.32 urn:nbn:de:0030-drops-239822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode