conference paper
Decidable problems for probabilistic automata on infinite words
published
yes
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Mathieu
Tracol
author 3F54FA38-F248-11E8-B48F-1D18A9856A87
KrCh
department
LICS: Logic in Computer Science
Modern Graph Algorithmic Techniques in Formal Verification
project
Rigorous Systems Engineering
project
Quantitative Graph Games: Theory and Applications
project
Microsoft Research Faculty Fellowship
project
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.
IEEE2012Dubrovnik, Croatia
eng
Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science
1107.209110.1109/LICS.2012.29
https://research-explorer.app.ist.ac.at/record/5384
Chatterjee, K., & Tracol, M. (2012). Decidable problems for probabilistic automata on infinite words. In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Dubrovnik, Croatia : IEEE. <a href="https://doi.org/10.1109/LICS.2012.29">https://doi.org/10.1109/LICS.2012.29</a>
Chatterjee K, Tracol M. 2012. Decidable problems for probabilistic automata on infinite words. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science
Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6280437, IEEE, 2012, doi:<a href="https://doi.org/10.1109/LICS.2012.29">10.1109/LICS.2012.29</a>.
Chatterjee K, Tracol M. Decidable problems for probabilistic automata on infinite words. In: <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2012. doi:<a href="https://doi.org/10.1109/LICS.2012.29">10.1109/LICS.2012.29</a>
K. Chatterjee, M. Tracol, in:, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2012.
K. Chatterjee and M. Tracol, “Decidable problems for probabilistic automata on infinite words,” in <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Dubrovnik, Croatia , 2012.
Chatterjee, Krishnendu, and Mathieu Tracol. “Decidable Problems for Probabilistic Automata on Infinite Words.” In <i>Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE, 2012. <a href="https://doi.org/10.1109/LICS.2012.29">https://doi.org/10.1109/LICS.2012.29</a>.
29572018-12-11T12:00:33Z2020-07-14T23:07:42Z