Decidable problems for unary PFAs

Rohit Chadha, Dileep Kini, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference 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 4 P (and hence in PSPACE).

Original languageEnglish (US)
Title of host publicationQuantitative Evaluation of Systems - 11th International Conference, QEST 2014, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages329-344
Number of pages16
ISBN (Print)9783319106953
DOIs
StatePublished - Jan 1 2014
Event11th International Conference on Quantitative Evaluation of Systems, QEST 2014 - Florence, Italy
Duration: Sep 8 2014Sep 10 2014

Publication series

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

Other

Other11th International Conference on Quantitative Evaluation of Systems, QEST 2014
CountryItaly
CityFlorence
Period9/8/149/10/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this