Probabilistic Automata on infinite words: decidability and undecidability results
Chatterjee K, Henzinger TA. 2010. Probabilistic Automata on infinite words: decidability and undecidability results. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6252, 1–16.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Corresponding author has ISTA affiliation
Department
Series Title
LNCS
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 an almost 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
2010-10-12
Publisher
Springer
Volume
6252
Page
1 - 16
Conference
ATVA: Automated Technology for Verification and Analysis
Conference Location
Singapore, Singapore
Conference Date
2010-09-21 – 2010-09-24
IST-REx-ID
Cite this
Chatterjee K, Henzinger TA. Probabilistic Automata on infinite words: decidability and undecidability results. In: Vol 6252. Springer; 2010:1-16. doi:10.1007/978-3-642-15643-4_1
Chatterjee, K., & Henzinger, T. A. (2010). Probabilistic Automata on infinite words: decidability and undecidability results (Vol. 6252, pp. 1–16). Presented at the ATVA: Automated Technology for Verification and Analysis, Singapore, Singapore: Springer. https://doi.org/10.1007/978-3-642-15643-4_1
Chatterjee, Krishnendu, and Thomas A Henzinger. “Probabilistic Automata on Infinite Words: Decidability and Undecidability Results,” 6252:1–16. Springer, 2010. https://doi.org/10.1007/978-3-642-15643-4_1.
K. Chatterjee and T. A. Henzinger, “Probabilistic Automata on infinite words: decidability and undecidability results,” presented at the ATVA: Automated Technology for Verification and Analysis, Singapore, Singapore, 2010, vol. 6252, pp. 1–16.
Chatterjee K, Henzinger TA. 2010. Probabilistic Automata on infinite words: decidability and undecidability results. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 6252, 1–16.
Chatterjee, Krishnendu, and Thomas A. Henzinger. Probabilistic Automata on Infinite Words: Decidability and Undecidability Results. Vol. 6252, Springer, 2010, pp. 1–16, doi:10.1007/978-3-642-15643-4_1.
Material in ISTA:
Earlier Version
Google Scholar