The decidability frontier for probabilistic automata on infinite words Technical Article


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Tracol, Mathieu
Title: The decidability frontier for probabilistic automata on infinite words
Affiliation IST Austria
Abstract: We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, B\"uchi, coB\"uchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words.
Publication Title: CoRR: Computing Research Repository
Publisher: ArXiv  
Date Published: 2011-04-01
Sponsor: This research was supported by the European Union project COMBEST, the European Network of Excellence ArtistDesign, the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE), and a Microsoft Faculty Fellowship
URL:
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    405 Henzinger
  2. Mathieu Tracol
    5 Tracol
Related IST Austria Work