Decidable problems for probabilistic automata on infinite words Conference Paper


Author(s): Chatterjee, Krishnendu; Tracol, Mathieu
Title: Decidable problems for probabilistic automata on infinite words
Affiliation IST Austria
Abstract: We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.
Keywords: almost and limit decision problems; Automata and formal languages; Parity conditions; Positive; Probabilistic automata
Conference Title: LICS: Logic in Computer Science
Conference Dates: June 25 - 28, 2012
Conference Location: Dubrovnik, Croatia
ISBN: 978-147998875-4
Publisher: IEEE  
Date Published: 2012-01-01
Start Page: 185
End Page: 194
URL:
DOI: 10.1109/LICS.2012.29
Open access: yes (repository)
IST Austria Authors
  1. Mathieu Tracol
    5 Tracol
Related IST Austria Work