zbMATH — the first resource for mathematics

On decision problems for probabilistic Büchi automata. (English) Zbl 1139.68030
Amadio, Roberto (ed.), Foundations of software science and computational structures. 11th international conference, FOSSACS 2008, held as part of the joint European conferences on theory and practice of software, ETAPS 2008, Budapest, Hungary, March 29–April 6, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78497-5/pbk). Lecture Notes in Computer Science 4962, 287-301 (2008).
Summary: 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.
For the entire collection see [Zbl 1133.68001].

68Q45 Formal languages and automata
03D35 Undecidability and degrees of sets of sentences
Full Text: DOI