Abstract
Hierarchical probabilistic automata (HPA) are probabilistic automata whose states are partitioned into levels such that for any state and input symbol, at most one transition with non-zero probability goes to a state at the same level, and all others go to states at a higher level. We present expressiveness and decidability results for 1-level HPAs that work on both finite and infinite length input strings; in a 1-level HPA states are divided into only two levels (0 and 1). Our first result shows that 1-level HPAs, with acceptance threshold 1/2 (both in the finite and infinite word cases), can recognize non-regular languages. This result is surprising in the light of the following two facts. First, all earlier proofs demonstrating the recognition of non-regular languages by probabilistic automata employ either more complex automata or irrational acceptance thresholds or HPAs with more than two levels. Second, it has been previously shown that simple probabilistic automata (SPA), which are 1-level HPAs whose accepting states are all at level 0, recognize only regular languages. We show that even though 1-level HPAs with threshold 1/2 are very expressive (in that they recognize non-regular languages), the non-emptiness and non-universality problems are both decidable in EXPTIME. To the best our knowledge, this is the first such decidability result for any subclass of probabilistic automata that accept non-regular languages. We prove that these decision problems are also PSPACE-hard. Next, we present a new sufficient condition when 1-level HPAs recognize regular languages (in both the finite and infinite cases). Finally, we show that the emptiness and universality problems for this special class of HPAs is PSPACE-complete.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baier, C., Größer, M.: Recognizing ω-regular languages with probabilistic automata. In: 20th IEEE Symp. on Logic in Computer Science, pp. 137–146 (2005)
Baier, C., Größer, M., Bertrand, N.: Probabilistic ω-automata. Journal of the ACM 59(1), 1–52 (2012)
Chadha, R., Sistla, A.P., Viswanathan, M.: On the expressiveness and complexity of randomization in finite state monitors. Journal of the ACM 56(5) (2009)
Chadha, R., Sistla, A.P., Viswanathan, M.: Probabilistic Büchi automata with non-extremal acceptance thresholds. In: Jhala, R., Schmidt, D. (eds.) VMCAI 2011. LNCS, vol. 6538, pp. 103–117. Springer, Heidelberg (2011)
Chadha, R., Sistla, A.P., Viswanathan, M.: Power of randomization in automata on infinite strings. Logical Methods in Computer Science 7(3), 1–22 (2011)
Chatterjee, K., Henzinger, T.A.: Probabilistic automata on infinite words: Decidability and undecidability results. In: Bouajjani, A., Chin, W.-N. (eds.) ATVA 2010. LNCS, vol. 6252, pp. 1–16. Springer, Heidelberg (2010)
Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: Symp. on Foundations of Computer Science, pp. 462–467 (1989)
Fijalkow, N., Gimbert, H., Oualhadj, Y.: Deciding the value 1 problem for probabilistic leaktight automata. In: IEEE Symp. on Logic in Computer Science, pp. 295–304 (2012)
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, Part II. LNCS, vol. 6199, pp. 527–538. Springer, Heidelberg (2010)
Größer, M.: Reduction Methods for Probabilistic Model Checking. PhD thesis, TU Dresden (2008)
Kemeny, J., Snell, J.: Denumerable Markov Chains. Springer (1976)
Paz, A.: Introduction to Probabilistic Automata. Academic Press (1971)
Rabin, M.O.: Probabilistic automata. Inf. and Control 6(3), 230–245 (1963)
Vardi, M.: Automatic verification of probabilistic concurrent finite-state programs. In: Symp. on Foundations of Computer Science, pp. 327–338 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chadha, R., Sistla, A.P., Viswanathan, M., Ben, Y. (2015). Decidable and Expressive Classes of Probabilistic Automata. In: Pitts, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2015. Lecture Notes in Computer Science(), vol 9034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46678-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-662-46678-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46677-3
Online ISBN: 978-3-662-46678-0
eBook Packages: Computer ScienceComputer Science (R0)