BBG-fossacs08

Ch. Baier, N. Bertrand, M. Groesser. On Decision Problems for Probabilistic Büchi Automata. In Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'08), LNCS, Volume 4962, Pages 287-301, Budapest, Hungary, March 2008.

Download [help]

Download paper: Doi page

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

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 omega-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

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/

BibTex Reference

@InProceedings{BBG-fossacs08,
   Author = {Baier, Ch. and Bertrand, N. and Groesser, M.},
   Title = {On Decision Problems for Probabilistic Büchi Automata},
   BookTitle = {Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS'08)},
   Volume = {4962},
   Pages = {287--301},
   Series = {LNCS},
   Publisher = {Springer},
   Address = {Budapest, Hungary},
   Month = {March},
   Year = {2008}
}

EndNote Reference [help]

Get EndNote Reference (.ref)