Probabilistic Buechi automata

Christel Baier
Friday, 30 May, 2008 (All day)

Probabilistic finite automata as acceptors for languages over finite words have been studied by many researchers. In this talk, we discuss probabilistic automata for recognizing languages over infinite words. The idea is to resolve the choices in a nondeterministic omega-automaton by probabilities and to require positive probabilities for the accepting runs. Surprisingly, probabilistic Buechi automata are more expressive than non-deterministic omega-automata. However, a certain subclass of probabilistic Buechi automata can be identified that has exactly the power of omega-regular languages. Concerning the efficiency, probabilistic omega-automata are not comparable with their nondeterministic counterparts. There are examples of omega-regular languages that have probabilistic Buechi automata of polynomial size, while any nondeterministic omega-automata with Streett, Rabin or Buechi acceptance is of exponential size.

The talk will introduce the formal notion of probabilistic automata with Buechi and other acceptance conditions and discuss some basic properties, such as expressiveness, efficiency, composition operations and decision problems.