On the Semantics and Complexity of Probabilistic Logic Programs
Authors: Fabio Gagliardi Cozman, Denis Deratani Mauá
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We examine the meaning and the complexity of probabilistic logic programs that consist of a set of rules and a set of independent probabilistic facts (that is, programs based on Sato s distribution semantics). We focus on two semantics, respectively based on stable and on well-founded models. We show that the semantics based on stable models (referred to as the credal semantics ) produces sets of probability measures that dominate infinitely monotone Choquet capacities; we describe several useful consequences of this result. We then examine the complexity of inference with probabilistic logic programs. We distinguish between the complexity of inference when a probabilistic program and a query are given (the inferential complexity), and the complexity of inference when the probabilistic program is fixed and the query is given (the query complexity, akin to data complexity as used in database theory). We obtain results on the inferential and query complexity for acyclic, stratified, and normal propositional and relational programs; complexity reaches various levels of the counting hierarchy and even exponential levels. |
| Researcher Affiliation | Academia | Fabio Gagliardi Cozman EMAIL Escola Politécnica, Universidade de São Paulo, Brazil Denis Deratani Mauá EMAIL Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil |
| Pseudocode | No | The paper describes algorithms in prose such as 'Given a plp P, PF and Q, initialize a and b with 0. For each total choice θ of probabilistic facts, compute the set Γ(θ) of all stable models of P, θ , and: if every stable model in Γ(θ) satisfies the truth values assigned by Q, then add P(θ) to a; if some stable model in Γ(θ) satisfies the truth values assigned by Q, then add P(θ) to b. Return [a, b] as the interval [P(Q) , P(Q)].' (page 8) and similar descriptions, but no clearly labeled 'Pseudocode' or 'Algorithm' blocks with structured code. |
| Open Source Code | No | The paper refers to the 'Prob Log package' and provides a URL: 'https://dtai.cs.kuleuven.be/problog/index.html' on page 5, but this is a third-party tool and not a statement or link to the authors' own implementation code for the methodology described in this paper. |
| Open Datasets | No | The paper uses illustrative examples (e.g., 'Example 1', 'Example 5') to explain concepts and demonstrate programs, but does not mention or use any publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper does not conduct experiments on datasets; therefore, no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity analysis; it does not describe experimental results or the hardware used for any computational tasks. |
| Software Dependencies | No | The paper mentions 'Prob Log package' (page 5) and references its website, but this is a third-party tool used for illustrative examples rather than a specific software dependency for the methodology described in the paper. No specific version numbers for any software components are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on the semantics and complexity of probabilistic logic programs; it does not contain details about experimental setup, hyperparameters, or training configurations. |