Recognizing $ømega$-regular Languages with Probabilistic Automata

Christel BaierChristel Baier, Marcus GrößerMarcus Größer

DOI Link

Christel Baier, Marcus Größer
Recognizing $ømega$-regular Languages with Probabilistic Automata
Proc. of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS), 137--146, 2005. IEEE Computer Society Press

Details
Bibtex

KurzfassungAbstract
Probabilistic finite automata as acceptors for languages over finite words have been studied by many researchers. In this paper, we show how probabilistic automata can serve as acceptors for /spl omega/-regular languages. Our main results are that our variant of probabilistic Buchi automata (PBA) is more expressive than non-deterministic /spl omega/-automata, but a certain subclass of PBA, called uniform PBA, has exactly the power of /spl omega/-regular languages. This also holds for probabilistic /spl omega/-automata with Streett or Rabin acceptance. We show that certain /spl omega/-regular languages have uniform PBA of linear size, while any nondeterministic Streett automaton is of exponential size, and vice versa. Finally, we discuss the emptiness problem for uniform PBA and the use of PBA for the verification of Markov chains against qualitative linear-time properties.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{BG2005,
  author    = {Christel Baier and Marcus Gr{\"{o}}{\ss}er},
  title     = {Recognizing ${\o}mega$-regular Languages with Probabilistic
               Automata},
  booktitle = {Proc. of the 20th Annual {IEEE} Symposium on Logic in Computer
               Science (LICS)},
  publisher = {IEEE Computer Society Press},
  year      = {2005},
  pages     = {137--146},
  doi       = {10.1109/LICS.2005.41}
}