Decidable problems for probabilistic automata on infinite words
From MaRDI portal
Abstract: We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether for every epsilon > 0 there is a word that is accepted with probability at least 1 - epsilon. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.
Recommendations
- Probabilistic automata on infinite words: decidability and undecidability results
- Probabilistic automata on finite words: decidable and undecidable problems
- Probabilistic automata over infinite words: expressiveness, efficiency, and decidability
- On Decision Problems for Probabilistic Büchi Automata
- Randomization in automata on infinite trees
Cited in
(29)- Undecidable problems for probabilistic automata of fixed dimension
- Decidable and expressive classes of probabilistic automata
- Probabilistic automata of bounded ambiguity
- Qualitative analysis of concurrent mean-payoff games
- When are emptiness and containment decidable for probabilistic automata?
- Deciding maxmin reachability in half-blind stochastic games
- Probabilistic automata and probabilistic logic
- Recurrence and transience for probabilistic automata
- Two recursively inseparable problems for probabilistic automata
- Deciding the value 1 problem for probabilistic leaktight automata
- Randomization in automata on infinite trees
- Decidable and expressive classes of probabilistic automata
- Deciding the value 1 problem for probabilistic leaktight automata
- Infinite Synchronizing Words for Probabilistic Automata
- The Effect of Tossing Coins in Omega-Automata
- Probabilistic automata on finite words: decidable and undecidable problems
- Probabilistic Acceptors for Languages over Infinite Words
- Probabilistic automata on infinite words: decidability and undecidability results
- When is containment decidable for probabilistic automata?
- A zero-one law for Markov chains
- Probabilistic automata of bounded ambiguity
- Probabilistic automata over infinite words: expressiveness, efficiency, and decidability
- Partial-observation stochastic games, how to win when belief fails
- Decidability conditions for problems about automata reading infinite words
- Profinite techniques for probabilistic automata and the Markov monoid algorithm
- On Decision Problems for Probabilistic Büchi Automata
- A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs
- A framework for belief-based programs and their verification
- CEGAR for compositional analysis of qualitative properties in Markov decision processes
This page was built for publication: Decidable problems for probabilistic automata on infinite words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986795)
