Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability

Christel Baier
(Technische Universität Dresden)
Nathalie Bertrand
(INRIA Rennes)
Marcus Größer
(Technische Universität Dresden)

Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (threshold semantics). The underlying notion of an accepting run can be defined as for standard omega-automata by means of a Buechi condition or other acceptance conditions, e.g., Rabin or Streett conditions. In this paper, we put the main focus on the probable semantics and provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, and decision problems.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 3–16.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.1 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org