On Decision Problems for Probabilistic Büchi Automata

DOI10.1007/978-3-540-78499-9_21zbMATH Open1139.68030OpenAlexW1494426349MaRDI QIDQ5458366FDOQ5458366

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of probabilistic verification
• Title not available (Why is that?)
• Probabilistic automata
• Title not available (Why is that?)
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Title not available (Why is that?)
• Automata, logics, and infinite games. A guide to current research
• The complexity of two-player games of incomplete information
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computer Aided Verification
• Quantitative Model Checking Revisited: Neither Decidable Nor Approximable
• Termination of Probabilistic Concurrent Program

Cited In (29)

• 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
• Probabilistic Weighted Automata
• Decidable and expressive classes of probabilistic 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
• Title not available (Why is that?)
• Decidable problems for probabilistic automata on infinite words
• 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
• Title not available (Why is that?)
• Randomness for free
• Title not available (Why is that?)
• Randomization in automata on infinite trees
• Recurrence and transience for finite probabilistic tables
• Power of Randomization in Automata on Infinite Strings
• When are emptiness and containment decidable for probabilistic automata?
• Perspective games
• Ambiguity, weakness, and regularity in probabilistic Büchi automata
• 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

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)