On Decision Problems for Probabilistic Büchi Automata

Christel BaierChristel Baier, Nathalie BertrandNathalie Bertrand, Marcus GrößerMarcus Größer

DOI Link

Christel Baier, Nathalie Bertrand, Marcus Größer
On Decision Problems for Probabilistic Büchi Automata
Proc. of the 11th International Conference on Foundations of Software Science and Computation Structures (FOSSACS), volume 4962 of Lecture Notes in Computer Science, 287--301, 2008. Springer

Details
Bibtex

KurzfassungAbstract
Probabilistic Büchi automata (PBA) are finite-state acceptors for infinite words where all choices are resolved by fixed distributions and where the accepted language is defined by the requirement that the measure of the accepting runs is positive. The main contribution of this paper is a complementation operator for PBA and a discussion on several algorithmic problems for PBA. All interesting problems, such as checking emptiness or equivalence for PBA or checking whether a finite transition system satisfies a PBA-specification, turn out to be undecidable. An important consequence of these results are several undecidability results for stochastic games with incomplete information, modelled by partially-observable Markov decision processes and ω-regular winning objectives. Furthermore, we discuss an alternative semantics for PBA where it is required that almost all runs for an accepted word are accepting, which turns out to be less powerful, but has a decidable emptiness problem.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-78499-9_21.

@inproceedings{BBG2008,
  author    = {Christel Baier and Nathalie Bertrand and Marcus Gr{\"{o}}{\ss}er},
  title     = {On Decision Problems for Probabilistic B{\"{u}}chi Automata},
  booktitle = {Proc. of the 11th International Conference on Foundations of
               Software Science and Computation Structures (FOSSACS)},
  series    = {Lecture Notes in Computer Science},
  volume    = {4962},
  publisher = {Springer},
  year      = {2008},
  pages     = {287--301},
  doi       = {10.1007/978-3-540-78499-9_21}
}