Resolving nondeterminism by chance

DOI10.4230/LIPICS.CONCUR.2025.32MaRDI QIDQ7310308zbMATH OpenFDO

Authors Soumyajit Paul, David Purser, Sven Schewe, Qiyi Tang, Patrick Totzke, Di-De Yen

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CONCUR.2025.32

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A bit of nondeterminism makes pushdown automata expressive and succinct
• Büchi complementation made tight
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Deciding the value 1 problem for probabilistic leaktight automata
• Degrees of ambiguity for parity tree automata
• Good for games automata: from nondeterminism to alternation
• Good-for-MDPs automata for probabilistic analysis and reinforcement learning
• History-deterministic timed automata
• History-deterministic timed automata
• History-deterministic timed automata are not determinizable
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 7471692 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• scientific article; zbMATH DE number 7799616 (Why is no real title available?)
• Lazy probabilistic model checking without determinisation
• Markov Chains
• Markov chains and unambiguous automata
• Minimising good-for-games automata is NP-complete
• Minimizing GFG Transition-Based Automata
• Model checking probabilistic systems
• On Determinisation of Good-for-Games Automata
• On the degree of ambiguity of finite automata
• Parameter synthesis for parametric probabilistic dynamical systems and prefix-independent specifications
• Positivity problems for low-order linear recurrence sequences
• Probabilistic automata of bounded ambiguity
• Probabilistic automata on finite words: decidable and undecidable problems
• Relating word and tree automata
• Relationships between nondeterministic and deterministic tape complexities
• Resolving nondeterminism with randomness
• Skolem and positivity completeness of ergodic Markov chains
• Solving Games Without Determinization
• Stochastic processes. An introduction.
• The 10,000 facets of MDP model checking
• The big-O problem
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Token games and history-deterministic quantitative automata
• Unambiguous finite automata over a unary alphabet
• Weak alternating automata are not that weak
• When are emptiness and containment decidable for probabilistic automata?

This page was built for publication: Resolving nondeterminism by chance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310308)