Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-20T09:40:16.290Z Has data issue: false hasContentIssue false
  • English
  • Français

Model checking with probabilistic tabled logic programming

Published online by Cambridge University Press:  05 September 2012

ANDREY GORLIN ,
C. R. RAMAKRISHNAN  and
SCOTT A. SMOLKA
ANDREY GORLIN
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA (e-mail: [email protected], [email protected], [email protected])
C. R. RAMAKRISHNAN
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA (e-mail: [email protected], [email protected], [email protected])
SCOTT A. SMOLKA
Affiliation:
Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA (e-mail: [email protected], [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a formulation of the problem of probabilistic model checking as one of query evaluation over probabilistic logic programs. To the best of our knowledge, our formulation is the first of its kind, and it covers a rich class of probabilistic models and probabilistic temporal logics. The inference algorithms of existing probabilistic logic-programming systems are well defined only for queries with a finite number of explanations. This restriction prohibits the encoding of probabilistic model checkers, where explanations correspond to executions of the system being model checked. To overcome this restriction, we propose a more general inference algorithm that uses finite generative structures (similar to automata) to represent families of explanations. The inference algorithm computes the probability of a possibly infinite set of explanations directly from the finite generative structure. We have implemented our inference algorithm in XSB Prolog, and use this implementation to encode probabilistic model checkers for a variety of temporal logics, including PCTL and GPL (which subsumes PCTL*). Our experiment results show that, despite the highly declarative nature of their encodings, the model checkers constructed in this manner are competitive with their native implementations.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 12 , Issue 4-5: 28th International Conference on Logic Programming , July 2012 , pp. 681 - 700
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baier, C. 1998. On Algorithmic Verification Methods for Probabilistic Systems. Habilitation Thesis, Fakultät für Mathematik & Informatik, Universität Mannheim.Google Scholar
Christiansen, H. and Gallagher, J. P. 2009. Non-discriminating arguments and their uses. In ICLP. LNCS, vol. 5649. 55–69.Google Scholar
Cleaveland, R., Iyer, S. P. and Narasimha, M. 2005. Probabilistic temporal logics via the modal mu-calculus. Theoretical Computer Science 342, 2-3, 316–350.CrossRefGoogle Scholar
De Raedt, L., Kimmig, A. and Toivonen, H. 2007. ProbLog: A probabilistic Prolog and its application in link discovery. In IJCAI. 2462–2467.Google Scholar
Delzanno, G. and Podelski, A. 1999. Model checking in CLP. In TACAS. 223–239.CrossRefGoogle Scholar
Du, X., Ramakrishnan, C. R. and Smolka, S. A. 2000. Tabled resolution + constraints: A recipe for model checking real-time systems. In IEEE RTSS.Google Scholar
Etessami, K. and Yannakakis, M. 2009. Recursive markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM 56, 1.Google Scholar
Farwer, B. and Leuschel, M. 2004. Model checking object Petri nets in prolog. In PPDP. 20–31.Google Scholar
Friedman, N., Getoor, L., Koller, D. and Pfeffer, A. 1999. Learning probabilistic relational models. In IJCAI. 1300–1309.Google Scholar
Getoor, L. and Taskar, B. 2007. Introduction to Statistical Relational Learning. The MIT Press.CrossRefGoogle Scholar
Gorlin, A., Ramakrishnan, C. R. and Smolka, S. A. 2012. Model checking with probabilistic tabled logic programming. Manuscript, available from http://www.cs.stonybrook.edu/~cram/probmc.CrossRefGoogle Scholar
Gupta, G., Bansal, A., Min, R., Simon, L. and Mallya, A. 2007. Coinductive logic programming and its applications. In ICLP. 27–44.Google Scholar
Gupta, G. and Pontelli, E. 1997. A constraint based approach for specification and verification of real-time systems. In Proceedings of the Real-Time Systems Symposium.Google Scholar
Gutmann, B., Jaeger, M. and Raedt, L. D. 2010. Extending ProbLog with continuous distributions. In Proceedings of ILP.Google Scholar
Gutmann, B., Thon, I., Kimmig, A., Bruynooghe, M. and Raedt, L. D. 2011. The magic of logical inference in probabilistic programming. TPLP 11, 4–5, 663–680.Google Scholar
Hansson, H. and Jonsson, B. 1994. A Logic for reasoning about time and reliability. Formal Aspects of Computing 6, 5, 512–535.CrossRefGoogle Scholar
Islam, M. A., Ramakrishnan, C. R. and Ramakrishnan, I. V. 2011. Inference in probabilistic logic programs with continuous random variables. ArXiv e-prints. http://arxiv.org/abs/1112.2681.Google Scholar
Itai, A. and Rodeh, M. 1981. Symmetry breaking in distributive networks. In FOCS. 150–158.Google Scholar
Kersting, K. and Raedt, L. D. 2000. Bayesian logic programs. In ILP Work-in-progress reports.Google Scholar
Kersting, K. and Raedt, L. D. 2001. Adaptive bayesian logic programs. In Proceedings of ILP.Google Scholar
Kozen, D. 1983. Results on the propositional μ-calculus. Theoretical Computer Science 27, 333–354.Google Scholar
Kucera, A., Esparza, J. and Mayr, R. 2006. Model checking probabilistic pushdown automata. Logical Methods in Computer Science 2, 1.Google Scholar
Kwiatkowska, M., Norman, G. and Parker, D. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In 23rd CAV. LNCS, vol. 6806. 585–591.Google Scholar
Milner, R. 1989. Communication and Concurrency. International Series in Computer Science. Prentice Hall.Google Scholar
Milner, R., Parrow, J. and Walker, D. 1992. A calculus of mobile processes, Parts I and II. Information and Computation 100 (1), 1–77.Google Scholar
Muggleton, S. 1996. Stochastic logic programs. In Advances in Inductive Logic Programming.Google Scholar
Mukhopadhyay, S. and Podelski, A. 1999. Beyond region graphs: Symbolic forward analysis of timed automata. In FSTTCS. 232–244.Google Scholar
Mukhopadhyay, S. and Podelski, A. 2000. Model checking for timed logic processes. In Computational Logic. 598–612.Google Scholar
Narman, P., Buschle, M., Konig, J. and Johnson, P. 2010. Hybrid probabilistic relational models for system quality analysis. In Proceedings of EDOC.CrossRefGoogle Scholar
Nilsson, U. and Maluszyński, J. 2000. Logic, Programming and Prolog. http://www.ida.liu.se/~ulfni/lpp.Google Scholar
Pemmasani, G., Ramakrishnan, C. R. and Ramakrishnan, I. V. 2002. Efficient model checking of real time systems using tabled logic programming and constraints. In International Conference on Logic Programming (ICLP). LNCS. Springer.Google Scholar
Poole, D. 2008. The independent choice logic and beyond. In Probabilistic ILP. 222–243.Google Scholar
Ramakrishna, Y. S., Ramakrishnan, C. R., Ramakrishnan, I. V., Smolka, S. A., Swift, T. and Warren, D. S. 1997. Efficient model checking using tabled resolution. In CAV. LNCS, vol. 1254. Springer, 143–154.Google Scholar
Ramakrishnan, C. R. 2001. A model checker for value-passing mu-calculus using logic programming. In PADL. LNCS, vol. 1990. Springer, 1–13.Google Scholar
Ramakrishnan, C. R. et al. 2000. XMC: A logic-programming-based verification toolset. In CAV. Number 1855 in LNCS. 576–580.Google Scholar
Richardson, M. and Domingos, P. 2006. Markov logic networks. Machine Learning.Google Scholar
Riguzzi, F. and Swift, T. 2010a. An extended semantics for logic programs with annotated disjunctions and its efficient implementation. In Italian Conference on Computational Logic. CEUR Workshop Proceedings, vol. 598.Google Scholar
Riguzzi, F. and Swift, T. 2010b. Tabling and answer subsumption for reasoning on logic programs with annotated disjunctions. In Technical Communications of the International Conference on Logic Programming. 162–171.Google Scholar
Riguzzi, F. and Swift, T. 2011. The PITA system: Tabling and answer subsumption for reasoning under uncertainty. TPLP 11, 4–5, 433–449.Google Scholar
SantosCosta, V. Costa, V., Page, D., Qazi, M. and Cussens, J. 2003. CLP(): Constraint logic programming for probabilistic knowledge. In Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI03). Acapulco, Mexico, 517–524.Google Scholar
Sarna-Starosta, B. and Ramakrishnan, C. R. 2003. Constraint-based model checking of data-independent systems. In International Conference on Formal Engineering Methods (ICFEM). Lecture Notes in Computer Science, vol. 2885. Springer, 579–598.Google Scholar
Sato, T. and Kameya, Y. 1997. PRISM: A symbolic-statistical modeling language. In IJCAI.Google Scholar
Singh, A., Ramakrishnan, C. R. and Smolka, S. A. 2008. A process calculus for mobile ad hoc networks. In 10th International Conference on Coordination Models and Languages (COORDINATION). LNCS, vol. 5052. Springer, 296–314.Google Scholar
Swift, T., Warren, D. S. et al. . 2012. The XSB logic programming system, Version 3.3. http://xsb.sourceforge.net.Google Scholar
Vennekens, J., Denecker, M. and Bruynooghe, M. 2009. CP-logic: A language of causal probabilistic events and its relation to logic programming. TPLP.CrossRefGoogle Scholar
Vennekens, J., Verbaeten, S. and Bruynooghe, M. 2004. Logic programs with annotated disjunctions. In ICLP. 431–445.Google Scholar
Wang, J. and Domingos, P. 2008. Hybrid Markov logic networks. In Proceedings of AAAI.Google Scholar
Wojtczak, D. and Etessami, K. 2007. PReMo: An analyzer for probabilistic recursive models. In TACAS.Google Scholar
Yang, P., Ramakrishnan, C. R. and Smolka, S. A. 2004. A logical encoding of the pi-calculus: Model checking mobile processes using tabled resolution. International Journal on Software Tools for Technology Transfer (STTT) 6, 1, 38–66.Google Scholar