Resolving nondeterminism with randomness

DOI10.4230/LIPICS.MFCS.2025.57MaRDI QIDQ7310232zbMATH OpenFDO

Authors Thomas A. Henzinger, Aditya Prakash, K. S. Thejaswini

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.57

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Hierarchy of Nondeterminism
• Büchi Good-for-Games Automata Are Efficiently Recognizable
• Checking history-determinism is NP-hard for parity automata
• From LTL to deterministic automata. A safraless compositional approach
• Good-for-MDPs automata for probabilistic analysis and reinforcement learning
• How deterministic are good-for-games automata?
• scientific article; zbMATH DE number 7799616 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Minimization and canonization of GFG transition-based automata
• Natural colors of Infinite words
• On Decision Problems for Probabilistic Büchi Automata
• On Determinisation of Good-for-Games Automata
• On semantically-deterministic automata
• Probabilistic automata on finite words: decidable and undecidable problems
• Probabilistic ω-automata
• Safraless Compositional Synthesis
• Solving Games Without Determinization
• Solving Sequential Conditions by Finite-State Strategies
• Stochastic Müller Games are PSPACE-Complete
• Testing and generating infinite sequences by a finite automaton
• Tighter construction of tight Büchi automata
• Token games and history-deterministic quantitative-automata

Cited in

(1)

• Resolving nondeterminism by chance

This page was built for publication: Resolving nondeterminism with randomness

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