Abstract
We present a monadic second-order logic which is extended by an expected value operator and show that this logic is expressively equivalent to probabilistic automata for both finite and infinite words. We give possible syntax extensions and an embedding of our probabilistic logic into weighted MSO logic. We further derive decidability results which are based on corresponding results for probabilistic automata.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
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össer, M.: Recognizing ω-regular languages with probabilistic automata. In: Proc. LICS, pp. 137–146. IEEE (2005)
Baier, C., Bertrand, N., Größer, M.: On Decision Problems for Probabilistic Büchi Automata. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 287–301. Springer, Heidelberg (2008)
Bollig, B., Gastin, P.: Weighted versus Probabilistic Logics. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 18–38. Springer, Heidelberg (2009)
Büchi, J.R.: Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6, 66–92 (1960)
Bukharaev, R.G.: Theorie der stochastischen Automaten. Teubner (1995)
Chadha, R., Sistla, A.P., Viswanathan, M.: Power of Randomization in Automata on Infinite Strings. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 229–243. Springer, Heidelberg (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)
Chatterjee, K., Doyen, L., Henzinger, T.A.: Probabilistic Weighted Automata. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 244–258. Springer, Heidelberg (2009)
Chatterjee, K., Henzinger, T.: 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)
Chatterjee, K., Tracol, M.: Decidable problems for probabilistic automata on infinite words. CoRR abs/1107.2091 (2011)
Cheung, L., Lynch, N., Segala, R., Vaandrager, F.: Switched PIOA: Parallel composition via distributed scheduling. TCS 365(1-2), 83–108 (2006)
Droste, M., Gastin, P.: Weighted automata and weighted logics. Theoretical Computer Science 380(1-2), 69–86 (2007)
Droste, M., Kuich, W., Vogler, H., (eds.): Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer (2009)
Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 98, 21–51 (1961)
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)
Klenke, A.: Probability Theory: A Comprehensive Course, 1st edn. Universitext. Springer (December 2007)
Mora-López, L., Morales, R., Sidrach de Cardona, M., Triguero, F.: Probabilistic finite automata and randomness in nature: a new approach in the modelling and prediction of climatic parameters. In: Proc. International Environmental Modelling and Software Congress, pp. 78–83 (2002)
Paz, A.: Introduction to Probabilistic Automata. Computer Science and Applied Mathematics. Academic Press, Inc. (1971)
Rabin, M.O.: Probabilistic automata. Information and Control 6(3), 230–245 (1963)
Ron, D., Singer, Y., Tishby, N.: The power of amnesia: Learning probabilistic automata with variable memory length. Machine Learning 25, 117–149 (1996)
Sakarovitch, J.: Rational and recognisable power series. In: Droste, et al. (eds.) [13] Handbook, pp. 105–174
Tracol, M., Baier, C., Größer, M.: Recurrence and transience for probabilistic automata. In: FSTTCS, vol. 4, pp. 395–406. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2009)
Vardi, M.Y.: Automatic verification of probabilistic concurrent finite state programs. In: Foundations of Computer Science, pp. 327–338 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Weidner, T. (2012). Probabilistic Automata and Probabilistic Logic. In: Rovan, B., Sassone, V., Widmayer, P. (eds) Mathematical Foundations of Computer Science 2012. MFCS 2012. Lecture Notes in Computer Science, vol 7464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32589-2_70
Download citation
DOI: https://doi.org/10.1007/978-3-642-32589-2_70
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32588-5
Online ISBN: 978-3-642-32589-2
eBook Packages: Computer ScienceComputer Science (R0)