TY - GEN

T1 - Emptiness under isolation and the value problem for hierarchical probabilistic automata

AU - Chadha, Rohit

AU - Sistla, A. Prasad

AU - Viswanathan, Mahesh

N1 - Funding Information:
We thanks the anonymous reviewers for their useful comments and suggestions. Rohit Chadha was partially supported by NSF CNS 1314338 and NSF CNS 1553548. A. Prasad Sistla was partially supported by NSF CCF 1319754 and NSF CNS 1314485. Mahesh Viswanathan was partially supported by NSF CNS 1314485.
Publisher Copyright:
© Springer-Verlag GmbH Germany 2017.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017

Y1 - 2017

N2 - k-Hierarchical probabilistic automata (k-HPA) are probabilistic automata whose states are stratified into k + 1 levels such that from any state, on any input symbol, at most one successor belongs to the same level, while the remaining belong to higher levels. Our main result shows that the emptiness and universality problems are decidable for k-HPAs with isolated cut-points; recall that a cut-point x is isolated if the acceptance probability of every word is bounded away from x. Our algorithm for establishing this result relies on computing an approximation of the value of an HPA; the value of a probabilistic automaton is the supremum of the acceptance probabilities of all words. Computing the exact value of a probabilistic automaton is an equally important problem and we show that the problem is co-R.E.-complete for k-HPAs, for k ≥ 2 (as opposed to Π20-complete for general probabilistic automata). On the other hand, we also show that for 1-HPAs the value can be computed in exponential time.

AB - k-Hierarchical probabilistic automata (k-HPA) are probabilistic automata whose states are stratified into k + 1 levels such that from any state, on any input symbol, at most one successor belongs to the same level, while the remaining belong to higher levels. Our main result shows that the emptiness and universality problems are decidable for k-HPAs with isolated cut-points; recall that a cut-point x is isolated if the acceptance probability of every word is bounded away from x. Our algorithm for establishing this result relies on computing an approximation of the value of an HPA; the value of a probabilistic automaton is the supremum of the acceptance probabilities of all words. Computing the exact value of a probabilistic automaton is an equally important problem and we show that the problem is co-R.E.-complete for k-HPAs, for k ≥ 2 (as opposed to Π20-complete for general probabilistic automata). On the other hand, we also show that for 1-HPAs the value can be computed in exponential time.

UR - http://www.scopus.com/inward/record.url?scp=85015846134&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015846134&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-54458-7_14

DO - 10.1007/978-3-662-54458-7_14

M3 - Conference contribution

AN - SCOPUS:85015846134

SN - 9783662544570

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 231

EP - 247

BT - Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Proceedings

A2 - Esparza, Javier

A2 - Murawski, Andrzej S.

PB - Springer

T2 - 20th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2017

Y2 - 22 April 2017 through 29 April 2017

ER -