The decidability frontier for probabilistic automata on infinite words
Chatterjee K, Henzinger TA, Tracol M. The decidability frontier for probabilistic automata on infinite words.
Download (ext.)
Preprint
| Submitted
| English
Department
Grant
Abstract
We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, 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.
Publishing Year
Date Published
2011-04-01
Page
19
IST-REx-ID
Cite this
Chatterjee K, Henzinger TA, Tracol M. The decidability frontier for probabilistic automata on infinite words.
Chatterjee, K., Henzinger, T. A., & Tracol, M. (n.d.). The decidability frontier for probabilistic automata on infinite words. ArXiv.
Chatterjee, Krishnendu, Thomas A Henzinger, and Mathieu Tracol. “The Decidability Frontier for Probabilistic Automata on Infinite Words.” ArXiv, n.d.
K. Chatterjee, T. A. Henzinger, and M. Tracol, “The decidability frontier for probabilistic automata on infinite words.” ArXiv.
Chatterjee K, Henzinger TA, Tracol M. The decidability frontier for probabilistic automata on infinite words.
Chatterjee, Krishnendu, et al. The Decidability Frontier for Probabilistic Automata on Infinite Words. ArXiv.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1104.0127
Google Scholar