Earlier Version

Decidable problems for probabilistic automata on infinite words

K. Chatterjee, M. Tracol, Decidable Problems for Probabilistic Automata on Infinite Words, IST Austria, 2011.

Download
OA IST-2011-004_IST-2011-0004.pdf 570.83 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
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 for every ε > 0 there is a word that is accepted with probability at least 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 words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions.
Publishing Year
Date Published
2011-04-11
Page
30
ISSN
IST-REx-ID

Cite this

Chatterjee K, Tracol M. Decidable Problems for Probabilistic Automata on Infinite Words. IST Austria; 2011. doi:10.15479/AT:IST-2011-0004
Chatterjee, K., & Tracol, M. (2011). Decidable problems for probabilistic automata on infinite words. IST Austria. https://doi.org/10.15479/AT:IST-2011-0004
Chatterjee, Krishnendu, and Mathieu Tracol. Decidable Problems for Probabilistic Automata on Infinite Words. IST Austria, 2011. https://doi.org/10.15479/AT:IST-2011-0004.
K. Chatterjee and M. Tracol, Decidable problems for probabilistic automata on infinite words. IST Austria, 2011.
Chatterjee K, Tracol M. 2011. Decidable problems for probabilistic automata on infinite words, IST Austria, 30p.
Chatterjee, Krishnendu, and Mathieu Tracol. Decidable Problems for Probabilistic Automata on Infinite Words. IST Austria, 2011, doi:10.15479/AT:IST-2011-0004.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
f5a0f664fadc335990f5fcf138df19f1


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar