The distribution semantics for normal programs with function symbols. (English) Zbl 1385.68022

Summary: The distribution semantics integrates logic programming and probability theory using a possible worlds approach. Its intuitiveness and simplicity have made it the most widely used semantics for probabilistic logic programming, with successful applications in many domains. When the program has function symbols, the semantics was defined for special cases: either the program has to be definite or the queries must have a finite number of finite explanations. In this paper we show that it is possible to define the semantics for all programs. We also show that this definition coincides with that of Sato and Kameya on positive programs. Moreover, we highlight possible approaches for inference, both exact and approximate.


68Q55 Semantics in the theory of computing
68N17 Logic programming
Full Text: DOI Link


[1] Dantsin, E., Probabilistic logic programs and their semantics, (Russian Conference on Logic Programming, LNCS, vol. 592, (1991), Springer), 152-164
[2] Poole, D., Logic programming, abduction and probability - a top-down anytime algorithm for estimating prior and posterior probabilities, New Gener. Comput., 11, 3, 377-400, (1993) · Zbl 0788.68025
[3] Sato, T., A statistical learning method for logic programs with distribution semantics, (Sterling, L., 12th International Conference on Logic Programming, Tokyo, Japan, (1995), MIT Press Cambridge, Massachusetts), 715-729
[4] Poole, D., The independent choice logic for modelling multiple agents under uncertainty, Artif. Intell., 94, 7-56, (1997) · Zbl 0902.03017
[5] Vennekens, J.; Verbaeten, S.; Bruynooghe, M., Logic programs with annotated disjunctions, (20th International Conference on Logic Programming, LNCS, vol. 3131, (2004), Springer Berlin, Heidelberg, Germany), 195-209 · Zbl 1104.68391
[6] De Raedt, L.; Kimmig, A.; Toivonen, H., Problog: a probabilistic prolog and its application in link discovery, (20th International Joint Conference on Artificial Intelligence, Hyderabad, India, IJCAI-05, vol. 7, (2007), AAAI Press Palo Alto, California, USA), 2462-2467
[7] Vennekens, J.; Denecker, M.; Bruynooghe, M., CP-logic: a language of causal probabilistic events and its relation to logic programming, Theory Pract. Log. Program., 9, 3, 245-308, (2009) · Zbl 1179.68025
[8] Sato, T.; Kameya, Y., Parameter learning of logic programs for symbolic-statistical modeling, J. Artif. Intell. Res., 15, 391-454, (2001) · Zbl 0994.68025
[9] Riguzzi, F.; Swift, T., Terminating evaluation of logic programs with finite three-valued models, ACM Trans. Comput. Log., 15, 4, 32:1-32:38, (2014) · Zbl 1354.68039
[10] Przymusinski, T., Every logic program has a natural stratification and an iterated least fixed point model, (ACM Conference on Principles of Database Systems, (1989)), 11-21
[11] Vlasselaer, J.; Van den Broeck, G.; Kimmig, A.; Meert, W.; De Raedt, L., Anytime inference in probabilistic logic programs with tp-compilation, (International Joint Conference on Artificial Intelligence, (2015)), 1852-1858
[12] Vlasselaer, J.; Van den Broeck, G.; Kimmig, A.; Meert, W.; De Raedt, L., Tp-compilation for inference in probabilistic logic programs, Int. J. Approx. Reason., 78, 15-32, (2016) · Zbl 1386.68174
[13] Sato, T.; Meyer, P., Tabling for infinite probability computation, (International Conference on Logic Programming, LIPIcs, vol. 17, (2012)), 348-358 · Zbl 1281.68191
[14] Sato, T.; Meyer, P., Infinite probability computation by cyclic explanation graphs, Theory Pract. Log. Program., 14, 909-937, (2014) · Zbl 1302.68054
[15] Gorlin, A.; Ramakrishnan, C. R.; Smolka, S. A., Model checking with probabilistic tabled logic programming, Theory Pract. Log. Program., 12, 4-5, 681-700, (2012) · Zbl 1260.68062
[16] Riguzzi, F.; Bellodi, E.; Lamma, E.; Zese, R.; Cota, G., Probabilistic logic programming on the web, Softw. Pract. Exp., (2015)
[17] Van Gelder, A.; Ross, K. A.; Schlipf, J. S., The well-founded semantics for general logic programs, J. ACM, 38, 3, 620-650, (1991) · Zbl 0799.68045
[18] Knopp, K., Theory and application of infinite series, Dover Books on Mathematics, (1951), Dover Publications · JFM 54.0222.09
[19] De Raedt, L.; Kimmig, A., Probabilistic (logic) programming concepts, Mach. Learn., 100, 1, 5-47, (2015) · Zbl 1346.68050
[20] Kolmogorov, A. N., Foundations of the theory of probability, (1950), Chelsea Publishing Company New York · Zbl 0074.12202
[21] Srivastava, S., A course on Borel sets, Graduate Texts in Mathematics, (2013), Springer
[22] Poole, D., Abducing through negation as failure: stable models within the independent choice logic, J. Log. Program., 44, 1-3, 5-35, (2000) · Zbl 0957.68013
[23] Poole, D., Probabilistic Horn abduction and Bayesian networks, Artif. Intell., 64, 1, 81-129, (1993) · Zbl 0792.68176
[24] Chow, Y.; Teicher, H., Probability theory: independence, interchangeability, martingales, Springer Texts in Statistics, (2012), Springer · Zbl 0652.60001
[25] Cohn, P., Basic algebra: groups, rings, and fields, (2003), Springer · Zbl 1003.00001
[26] Willard, S., General topology, Addison-Wesley Series in Mathematics, (1970), Dover Publications · Zbl 0205.26601
[27] Steen, L.; Seebach, J., Counterexamples in topology, Dover Books on Mathematics, (2013), Dover Publications · Zbl 0211.54401
[28] Milch, B.; Marthi, B.; Russell, S. J.; Sontag, D.; Ong, D. L.; Kolobov, A., BLOG: probabilistic models with unknown objects, (Kaelbling, L. P.; Saffiotti, A., IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005, (2005), Professional Book Center), 1352-1359
[29] Poole, D., The independent choice logic and beyond, (De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S., Probabilistic Inductive Logic Programming, LNCS, vol. 4911, (2008), Springer Berlin, Heidelberg), 222-243 · Zbl 1137.68596
[30] Mantadelis, T.; Janssens, G., Nesting probabilistic inference, corr
[31] Kimmig, A.; Demoen, B.; De Raedt, L.; Costa, V. S.; Rocha, R., On the implementation of the probabilistic logic programming language problog, Theory Pract. Log. Program., 11, 2-3, 235-262, (2011) · Zbl 1220.68037
[32] Riguzzi, F., MCINTYRE: a Monte Carlo system for probabilistic logic programming, Fundam. Inform., 124, 4, 521-541, (2013)
[33] N.D. Goodman, J. B. Tenenbaum. Probabilistic models of cognition [online, cited 15 April 2016].
[34] Riguzzi, F.; Swift, T., The PITA system: tabling and answer subsumption for reasoning under uncertainty, Theory Pract. Log. Program., 11, 4-5, 433-449, (2011) · Zbl 1218.68169
[35] Riguzzi, F.; Swift, T., Well-definedness and efficient inference for probabilistic logic programming under the distribution semantics, 25th Annual GULP Conference, Theory Pract. Log. Program., 13, Special Issue 02, 279-302, (2013) · Zbl 1267.68084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.