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).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, M., Akshay, S., Genest, B., Thiagarajan, P.S.: Approximate verification of the symbolic dynamics of markov chains. In: LICS, pp. 55–64 (2012)
Allender, E., Bürgisser, P., Kjeldgaard-Pedersen, J., Bro Miltersen, P.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987–2006 (2009)
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)
Bertoni, A.: The solution of problems relative to probabilistic automata in the frame of formal language theory. In: Siefkes, D. (ed.) GI 1974. LNCS, vol. 26, pp. 107–112. Springer, Heidelberg (1975)
Chadha, R., Sistla, A.P., Viswanathan, M.: Probabilistic automata with isolated cut-points. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 254–265. Springer, Heidelberg (2013)
Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: 30th Annual Symposium on Foundations of Computer Science, pp. 462–467 (1989)
Doyen, L., Henzinger, T.A., Raskin, J.-F.: Equivalence of labeled markov chains. Inernational Journal of Foundations of Computer Science 19(3), 549–563 (2008)
Gantmacher, F.R.: Applications of the Theory of Matrices. Dover Books on Mathematics Series, Dover (2005)
Gimbert, H., Oualhadj, Y.: Probabilistic automata on finite words: Decidable and undecidable problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 527–538. Springer, Heidelberg (2010)
Gramlich, G.: Probabilistic and nondeterministic unary automata. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 460–469. Springer, Heidelberg (2003)
Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: Language equivalence for probabilistic automata. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 526–540. Springer, Heidelberg (2011)
Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J.: On the complexity of the equivalence problem for probabilistic automata. In: Birkedal, L. (ed.) FOSSACS 2012. LNCS, vol. 7213, pp. 467–481. Springer, Heidelberg (2012)
Korthikanti, V.A., Viswanathan, M., Agha, G., Kwon, Y.: Reasoning about mdps as transformers of probability distributions. In: QEST, pp. 199–208 (2010)
Kwon, Y., Agha, G.: Linear Inequality LTL (iLTL): A Model Checker for Discrete Time Markov Chains. In: Davies, J., Schulte, W., Barnett, M. (eds.) ICFEM 2004. LNCS, vol. 3308, pp. 194–208. Springer, Heidelberg (2004)
Kwon, Y.M., Agha, G.: A Markov Reward Model for Software Reliability. In: IEEE International Parallel and Distributed Processing Symposium, IPDPS 2007, pp. 1–6 (2007)
Norris, J.R.: Markov Chains. Cambridge University Press (1997)
Paz, A.: Introduction to probabilistic automata. Academic Press (1971)
Rabin, M.O.: Probabilistic automata. Information and Computation 6(3), 230–245 (1963)
Rutten, J.M., Kwiatkowska, M., Norman, G., Parker, D.: Mathematical Techniques for Analyzing Concurrent and Probabilistic Systems. AMS (2004)
Salomaa, A., Soittola, M., Bauer, F.L., Gries, D.: Automata-theoretic aspects of formal power series. Texts and monographs in computer science. Springer (1978)
Schönhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 520–529. Springer, Heidelberg (1979)
Schützenberger, M.P.: On the definition of a family of automata. Information and Control 4(2-3), 245–270 (1961)
Senata, E.: Non-negative Matrices and Markov Chains. George Allen & Unwin Ltd. (1973)
Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time: Preliminary report. In: Proc. of the 5th Ann. ACM Symposium on Theory of Computing, pp. 1–9 (1973)
Turakainen, P.: On stochastic languages. Information and Control 12(4), 304–313 (1968)
Tzeng, W.-G.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21(2), 216–227 (1992)
Wagner, K.W.: Some observations on the connection between counting and recursion. Theoretical Computer Science 47(3), 131–147 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Chadha, R., Kini, D., Viswanathan, M. (2014). Decidable Problems for Unary PFAs. In: Norman, G., Sanders, W. (eds) Quantitative Evaluation of Systems. QEST 2014. Lecture Notes in Computer Science, vol 8657. Springer, Cham. https://doi.org/10.1007/978-3-319-10696-0_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-10696-0_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10695-3
Online ISBN: 978-3-319-10696-0
eBook Packages: Computer ScienceComputer Science (R0)