Decidable problems for unary PFAs

Rohit Chadha; Dileep Kini; Mahesh Viswanathan

doi:10.1007/978-3-319-10696-0_26

Decidable problems for unary PFAs

Rohit Chadha, Dileep Kini, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 ₄ P (and hence in PSPACE).

Original language	English (US)
Title of host publication	Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings
Publisher	Springer-Verlag Berlin Heidelberg
Pages	329-344
Number of pages	16
ISBN (Print)	9783319106953
DOIs	https://doi.org/10.1007/978-3-319-10696-0_26
State	Published - Jan 1 2014
Event	11th International Conference on Quantitative Evaluation of Systems, QEST 2014 - Florence, Italy Duration: Sep 8 2014 → Sep 10 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8657 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	11th International Conference on Quantitative Evaluation of Systems, QEST 2014
Country	Italy
City	Florence
Period	9/8/14 → 9/10/14

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-10696-0_26

Fingerprint Dive into the research topics of 'Decidable problems for unary PFAs'. Together they form a unique fingerprint.

Cite this

Chadha, R., Kini, D., & Viswanathan, M. (2014). Decidable problems for unary PFAs. In Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings (pp. 329-344). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8657 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-319-10696-0_26

Decidable problems for unary PFAs. / Chadha, Rohit; Kini, Dileep; Viswanathan, Mahesh.

Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings. Springer-Verlag Berlin Heidelberg, 2014. p. 329-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8657 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chadha, R, Kini, D & Viswanathan, M 2014, Decidable problems for unary PFAs. in Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8657 LNCS, Springer-Verlag Berlin Heidelberg, pp. 329-344, 11th International Conference on Quantitative Evaluation of Systems, QEST 2014, Florence, Italy, 9/8/14. https://doi.org/10.1007/978-3-319-10696-0_26

Chadha R, Kini D, Viswanathan M. Decidable problems for unary PFAs. In Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings. Springer-Verlag Berlin Heidelberg. 2014. p. 329-344. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-10696-0_26

Chadha, Rohit ; Kini, Dileep ; Viswanathan, Mahesh. / Decidable problems for unary PFAs. Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings. Springer-Verlag Berlin Heidelberg, 2014. pp. 329-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2137b7ea72b94494a2fd89021f3d4258,

title = "Decidable problems for unary PFAs",

abstract = "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).",

author = "Rohit Chadha and Dileep Kini and Mahesh Viswanathan",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-10696-0_26",

language = "English (US)",

isbn = "9783319106953",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "329--344",

booktitle = "Quantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings",

note = "11th International Conference on Quantitative Evaluation of Systems, QEST 2014 ; Conference date: 08-09-2014 Through 10-09-2014",

}

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 -