On Decision Problems for Probabilistic Büchi Automata

DOI10.1007/978-3-540-78499-9_21MaRDI QIDQ5458366zbMATH OpenOpenAlexFDO

Authors Nathalie Bertrand, Marcus Grösser, Christel Baier

Publication date 11 April 2008

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78499-9_21

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Probabilistic automata on infinite words: decidability and undecidability results
• Decidable problems for probabilistic automata on infinite words
• scientific article; zbMATH DE number 1822394
• Power of randomization in automata on infinite strings
• Probabilistic automata on finite words: decidable and undecidable problems

Cites work

• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 729460 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 846904 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3240812 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• Automata, logics, and infinite games. A guide to current research
• Computer Aided Verification
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Probabilistic automata
• Quantitative Model Checking Revisited: Neither Decidable Nor Approximable
• Termination of Probabilistic Concurrent Program
• The complexity of probabilistic verification
• The complexity of two-player games of incomplete information

Cited in

(30)

• Model checking hyperproperties for Markov decision processes
• Weighted versus Probabilistic Logics
• What is decidable about partially observable Markov decision processes with \(\omega\)-regular objectives
• Recurrence and transience for probabilistic automata
• Decidable and expressive classes of probabilistic automata
• Probabilistic Weighted Automata
• Probabilistic Büchi automata with non-extremal acceptance thresholds
• Verification and control of partially observable probabilistic real-time systems
• Verification and control of partially observable probabilistic systems
• Reachability analysis of quantum Markov decision processes
• Decidable problems for probabilistic automata on infinite words
• scientific article; zbMATH DE number 1786649 (Why is no real title available?)
• Probabilistic automata on infinite words: decidability and undecidability results
• CEGAR for compositional analysis of qualitative properties in Markov decision processes
• Model checking linear-time properties of probabilistic systems
• scientific article; zbMATH DE number 3854424 (Why is no real title available?)
• Randomness for free
• scientific article; zbMATH DE number 1822394 (Why is no real title available?)
• Recurrence and transience for finite probabilistic tables
• A PSPACE algorithm for almost-sure rabin objectives in multi-environment MDPs
• Randomization in automata on infinite trees
• Power of Randomization in Automata on Infinite Strings
• When are emptiness and containment decidable for probabilistic automata?
• Ambiguity, weakness, and regularity in probabilistic Büchi automata
• Perspective games
• The Effect of Tossing Coins in Omega-Automata
• Partial-observation stochastic games, how to win when belief fails
• Probabilistic Acceptors for Languages over Infinite Words
• A survey of partial-observation stochastic parity games
• Power of randomization in automata on infinite strings

Describes a project that uses

Uses Software

• POMDP

This page was built for publication: On Decision Problems for Probabilistic Büchi Automata

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