TY - GEN
T1 - Decidable problems for unary PFAs
AU - Chadha, Rohit
AU - Kini, Dileep
AU - Viswanathan, Mahesh
PY - 2014/1/1
Y1 - 2014/1/1
N2 - Given a PFA A and a cut-point λ, the isolation problem asks if there is a bound ε > 0 such that the acceptance probability of every word is bounded away from λ by ε. In this paper we show that the isolation problem for PFAs with a unary input alphabet is (a) coNPcomplete, if the cut-point is 0 or 1, and (b) is in coNP RP and coNP-hard, if the cut-point is in (0, 1). We also show that the language containment problem, language equivalence problem, the emptiness problem and the universality problem for unary PFAs with limit isolated cut-points is in the fourth level of counting hierarchy C 4 P (and hence in PSPACE).
AB - Given a PFA A and a cut-point λ, the isolation problem asks if there is a bound ε > 0 such that the acceptance probability of every word is bounded away from λ by ε. In this paper we show that the isolation problem for PFAs with a unary input alphabet is (a) coNPcomplete, if the cut-point is 0 or 1, and (b) is in coNP RP and coNP-hard, if the cut-point is in (0, 1). We also show that the language containment problem, language equivalence problem, the emptiness problem and the universality problem for unary PFAs with limit isolated cut-points is in the fourth level of counting hierarchy C 4 P (and hence in PSPACE).
UR - http://www.scopus.com/inward/record.url?scp=84907363562&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84907363562&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-10696-0_26
DO - 10.1007/978-3-319-10696-0_26
M3 - Conference contribution
AN - SCOPUS:84907363562
SN - 9783319106953
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 329
EP - 344
BT - Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings
PB - Springer-Verlag Berlin Heidelberg
T2 - 11th International Conference on Quantitative Evaluation of Systems, QEST 2014
Y2 - 8 September 2014 through 10 September 2014
ER -