Probabilistic logic programming extends logic programming to ofer a rich specification language for statistical relational models and, more recently, to neurosymbolic reasoners. The standard stable model semantics adopted by probabilistic logic programs collapses in the presence of contradictions that can arise when knowledge is not carefully elicited. In this work, we study probabilistic disjunctive logic programs under the least-undefined stable model semantics. We prove missing complexity results for logic inference with bounded-arity predicates, and then derive the complexity of probabilistic inference with respect to both the credal and the maximum entropy semantics.
The construction of a knowledge base may produce
contradictions, for instance, when several experts are consulted,
or when rules are extracted automatically [
maleAdult(barber). shaves(barber, ) ←
maleAdult(), not shaves(, ).
There is no stable model here, for if the barber shaves himself then shaves(barber, barber) is not enforced by the rule; and if the barber does not shave himself, then shaves(barber, barber) must be true. Yet the rule produces the sensible inference shaves(barber, john).
We can handle such contradictions gracefully through a
three-valued semantics where facts may be left undefined [
Probabilistic logic programming languages [
likes(, ), likes(, ). 22nd International Workshop on Nonmonotonic Reasoning, November 2–4, 2024, Hanoi, Vietnam * Corresponding author. $ ddm@ime.usp.br (D. D. Mauá); fgcozman@usp.br (F. G. Cozman); agarces2@mit.edu (A. Garces) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The program states that Anna likes Bob with probability 0.01, that Bob likes Carl, and that liking is transitive. The distribution semantics assigns a probability distribution over two logic programs: one containing the fact likes(anna, bob) and the remaining facts and rules, with probability 0.01, and another one that does not contain that fact, with probability 0.99. Thus, considering the minimal model semantics for the logic programs, the probabilistic program infers that likes(anna, carl) is true with probability 0.01.
The distribution semantics is appealing for its simplicity
and for separating the logic and probabilistic parts, which
enables diferent combinations of logic and probabilistic
semantics. And while such a combination can be made in a
number of diferent forms [
Targeting the modeling of probabilistic argumentative
knowledge, which often contains contradictions, Totis,
Kimmig and De Raedt [
LPMLN [
Hadjichristodoulou and Warren [
Another path has been followed by Rocha and Cozman
[
To summarize: the L-stable semantics handles
inconsistencies so as to minimize the number of undefined atoms, in
a way that is consistent with the distribution semantics,
coincides with the widely adopted stable model semantics in the
lack of contradictions, and as such is able to also represent
non-determinism (i.e., multiple intended models/solutions).
In addition, the L-stable semantics is also akin to typical
semantics of abstract argumentation frameworks [
To make the probabilistic language applicable, one needs to derive inference algorithms that take a probabilistic logic program and a target atom and produce the probabilities of that atom being true according to the given semantics. When designing such algorithms, is useful to classify such inference tasks with respect to their computational complexity class.
In this work, we study the computational complexity of
probabilistic logic programming under the L-stable
semantics. We first prove some missing results about the
complexity of (non-probabilistic) logic programs with bounded-arity
predicates. More precisely, we show that marginal
inference under the L-stable semantics is Σ 3-hard for normal
programs and Σ 4-hard for disjunctive programs, thus
climbing one step of the polynomial hierarchy with respect to
the stable model semantics [
The credal semantics [
The maximum entropy semantics averages all probability
models and produces a sharp probability value [
We also address a more practical aspect of inference
under the L-stable semantics. We use a known relation [
The rest of this paper is organized as follows. We start by reviewing some basic facts about logic programming and probabilistic logic programming (Section 2). We then prove complexity results first for logic programs (Section 3) and then for probabilistic logic programs (Section 4). In Section 5, we discuss the practical inference algorithm for probabilistic programs and the empirical results comparing definedness of L-stable semantics and smProbLog. Final remarks conclude this paper (Section 6).
We assume the reader is familiar with logic programming
and refer to [
A rule is an expression of the form 1 ∨ · · · ∨ ←
1, . . . , , not +1, . . . , not , where and are atoms, > 0 (note: this disallows integrity constraints) and , ≥ 0. We define head() = {1, . . . , }, body+() = {1, . . . , }, body− () = {+1, . . . , }, and body() = body+() ∪ body− (). A rule is normal if = 1. It is a fact if in addition = = 0. In general, facts provide input data and rules derive new data or verify properties of the input data. A disjunctive logic program, or simply a program, is a finite set of rules. We denote the set of facts of a program by facts( ). The program is normal if and only if all rules are normal.
The semantics of a program with variables is given by the semantics of its grounding, so for the rest of this section we consider only propositional programs.
The Herbrand base of a program is the set formed by all ground atoms that can be built using predicate names and constants in the program. The grounding of a program is the propositional program obtained by grounding each rule, that is, replacing variables with constants from the Herbrand base in every consistent way. Let t, f and u denote ground atoms which do not occur in a program . A three-valued interpretation is a function from the atoms in the Herbrand base to f < u < t. We extend so that () = for = t, u, f, (¬) = t if () = f, () = f if () = t and (¬) = u if () = u. We say that is defined if () ̸= u. We write = { | () = } for = t, f, u. An interpretation is total if u = ∅. We define (head()) = max{() | ∈ head()} and (body()) as the minimum of min{() | ∈ body+()} and min{(¬) | ∈ body− ()}. An interpretation satisfies a rule if (head()) ≥ (body()). Equivalently, the rule is satisfied by if and only if: (S1) The rule body contains a false literal, that is, if either body+() ∩ f ̸= ∅ or body− () ∩ t ̸= ∅; or (S2) The literals in the body are all satisfied (i.e., true if positive, false if negative), and the head has at least one atom which is true; or (S3) Each literal in the body is either satisfied or undefined, some literal is the body is undefined, and some atom in the head is either satisfied or undefined.
The last rule is what diferentiates three-valued semantics, such as the L-stable semantics, from two-valued semantics, such as the stable semantics, as it allows local inconsistency introduced by a rule to be resolved by an undefined atom in the body and/or an undefined atom in the head. Note that, by definition, a fact can only be satisfied by (S2).
Example 1. The interpretation () = t and () = () = f satisfies the rule ∨ ← , not . by (S1); the interpretation () = f and () = () = t satisfies that same rule by (S2); last, the valuation () = u, () = t and () = f satisfies that rule by (S3).
An interpretation is a model of a program if it satisfies all
of its rules. We define a partial order ≤ (reflexive,
antisymmetric and transitive) of interpretations as: 0 ≤ 1 if and
only if 0() ≤ 1() for all . A model 1 is minimal if
there is no model 0 ≤ 1 such that 0 ̸= 1. If is total
then it is minimal if and only if t is ⊆ -minimal. Note that
by (S3) if t = f = ∅, then is a model as it satisfies all
rules (and we disallow integrity constraints). Thus, since
≤ is a partial order and the Herbrand base is finite, every
normal program admits one or more minimal models [
The stability of a model is connected to the notion
of the program’s reduct w.r.t. , written /, obtained by
the so-called the modified Gelfond–Lifschitz (mGL)
transformation [
Example 2. Table 1 lists the interpretations = ((), ()), the respective program reduct and minimal models for the program ∨ .
←
To see why the program does not have stable models, note that the three normal rules induce a contradiction on the truthvalue of each atom (this can be seen as a 2-coloring of an order 3 complete graph whose nodes are the atoms). Additionally, interpreting any of , or as undefined leads the others to also be interpreted as undefined (due to the cycle). But this violates the disjunction.
While joint use of disjunction and negation can create inconsistent programs, disjunction can also be used to avoid the need of contradictions to discard interpretations: Example 4. To see another important feature of the stable semantics, consider the following program, which describes the property of 3-colorability of a given undirected graph. edge(a, b). edge(a, c). edge(b, d). edge(c, d). eq(r, r). eq(g, g). eq(b, b).
As the underlying graph is 3-colorable, the program admits a total stable model where fail is false. Now consider a modiifcation of the facts so that the graph is not 3-colorable (e.g., by adding the fact edge(b, c)). Then any (stable) model must assign fail to true and therefore must also assign color(, ) to true for any node and color . But such a model is maximal (it assigns the maximum number of true atoms); hence it is only stable, if there is not other stable model. It follows that there is a stable model defining colorable as true if and only if the graph is 3-colorable.
This type of modeling feature is called saturation, and
is important to achieve more computation power in the
representation [
Example 5. We can specify a random graph of order 3 as: 0.5 :: arc(a, b). 0.5 :: arc(a, c). 0.5 :: arc(b, c).
The semantics of a probabilistic program is given by its grounding. Thus, we consider only grounded programs in the rest of this section. A total choice is any subset of the facts. Given a total choice ⊆ facts( ), we denote the subsequent (deterministic) logic program by = ( ∖ facts( )) ∪ . A probabilistic program induces a distribution over logic programs by
Pr( ) = ∏︁ ( ) ∏︁
(1 − ( )) . ∈
∈facts( )∖ That is, the logic program assumes that each fact ∈ facts( ) is selected independently with probability ( ) in the resulting random logic programs. Note that because we assumed that probabilistic facts do not unify with rule heads, and because under minimal model semantics an atom is true only if it appears as a fact or in the head of rule, then an atom in a probabilistic fact is true if it is selected by a total choice. That is, a total choice is equivalent to fixing the interpretation of a probabilistic atom.
Let ∼ denote an interpretation that agrees with , i.e., t ∩ facts( ) = and f ∩ facts( ) = facts( ) ∖ . The probabilistic semantics can be extended to interpretations of the remaining atoms of the Herbrand base by probabilistic models. A probabilistic model is a probability measure over the interpretations such that (PM1) Pr() > 0 only if ∈ models( ) for ∼ , and (PM2) Pr({ ∼ }) = Pr( ).
Thus, if for some total choice the induced logic program has no L-stable model, then by (PM1) Pr() = 0 for any ∼ , which contradicts (PM2). We call such a program inconsistent.
The probabilistic model semantics is only defined for
consistent programs, and a consistent probabilistic program
admits one or more probabilistic models. When there are
many probabilistic models, there are generally two ways of
attributing a semantics. The credal semantics [
Given a probabilistic model, a target atom and a list of evidence literals = {1, . . . , }, all in the Herbrand base of the program, we define a probabilistic inference as the computation of the conditional probability Pr(|), where Pr(1, . . . , ) = ∑︀|=1,..., Pr() for any list of literals . For semantics that admit more than one probabilistic model, we are interested in obtaining tight upper and lower bounds on such probabilities: Pr(|) = min Pr(|),
Pr
Pr(|) = max Pr(|).
Pr
For semantics which produce a single probability value, a
conditional probability can be obtained as the ratio of two
joint probability events, Pr(, ) and Pr(), so that there
is no loss in focusing on the computation of the marginal
probability of an atom. This is not the case for multivalued
semantics such as the credal semantics. However, due to its
structure, the credal semantics do admit a similar
decomposition [
Pr(|) =
Pr(, ) Pr(, ) + Pr(¬, ) .
A similar expression can be obtained for Pr(|), noting that Pr(|) = 1 − Pr(¬|). Additionally, the marginal lower and upper probabilities according to the credal semantics satisfy:
Pr() = Pr() =
∑︁ :∀∼ ,|=
∑︁ :∃∼ ,|=
Pr( ), Pr( ).
That is, the lower probability collects the probabilities of
total choices that induce a logic program of which is a
cautious consequence, while the upper probability collects
the probabilities of logic programs of which is a brave
consequence. Credal semantics thus extends the cautious/brave
reasoning strategies of answer set programming [
0.1 :: . 0.3 :: . ← ← .
← not .
. ← not .
The total choices, their distribution, and the L-stable models of the induced programs (denoted as tuples ((), (), (), ()) are listed in Table 2. The credal semantics yields Pr() ∈ [0.1, 0.73] and the MaxEnt semantics yields Pr() = 0.415. Also, we have that Pr(¬) = 0, which implies that credal and MaxEnt semantics coincide for that inference, and also that the probability that is undefined is 1 − 0.415 = 0.585, under the MaxEnt semantics. This value can be taken as a measure of inconsistency of the program w.r.t. atom .
Computational complexity classifies computational
problems according to the type of resources and machines needed
to solve them. This section collects basic definitions of
concepts related to computational complexity theory. We point
the reader to [
A language is a set of strings, and a complexity class is
a set of languages. For some complexity class , a decision
problem accepts or rejects strings and can be viewed as a
language. Then is -hard if every problem ′ in the
complexity class can be (many-one) reduced in polynomial
time to (that is, there is an algorithm that takes the input
to ′, modifies it with polynomial efort, calls with the
modified input, and then accepts or rejects ). If is in
and is -hard, then is -complete. An oracle Turing
machine Mℒ is a Turing machine with additional tapes, such
that it can write a string to a tape and obtain from the oracle,
in another tape and in unit time, the decision as to whether
∈ ℒ or not. If a class of languages is defined by a set of
Turing machines M (that is, the languages are decided by
these machines), then define ℒ to consist of the languages
defined by oracle machines in {Mℒ : M ∈ ℳ}. If and ′
are sets of languages, ′ = ∪ℒ∈′ ℒ. We use well-known
complexity classes P, NP, coNP. The Polynomial
Hierarchy [
When discussing complexity results in the following, we consider always the decision versions of the inference problems, e.g. deciding whether min / max Pr() ≥ for some rational and atom . 3. Complexity of Logic Programs The first contribution of this work is to provide some missing results about the computational complexity of inference in (deterministic) logic programs under the L-stable semantics.
The complexity of logic programs under the total stable
model semantics has been thoroughly analyzed in the
literature, both in terms of the expressivity of the language (i.e.,
the presence of negation, disjunction, aggregation, etc) and
the program structure (i.e., its dependency graph) [
Eiter, Leone and Saccà [
The complexity of non-propositional logic programs under the L-stable semantics has been open. The next results ifll that gap. We start with the complexity of normal logic programs with bounded-arity predicates.
Theorem 1. Deciding if there is an L-stable model satisfying a given atom for a normal program with bounded-arity predicates is Σ 3-hard.
Proof. Hardness is shown by a many-one reduction from
the canonical Σ 3-complete problem of deciding satisfiability
of a 3-Quantified Boolean Formula (3-QBF) [
∃1, . . . , ∀1, . . . , ∃1, . . . , , where is in 3-CNF with clauses 1, . . . , .
We encode each literal over and by a predicate lit(, , ), where ∈ {, }, is the corresponding variable subindex and is 0 if the literal is negated (i.e., ¬1) and 1 otherwise. For any such variable, insert the rules lit(, , ) ←
not lit(, , ), ̸= .
That rule creates a bijection between L-stable models and configurations , of the variables and . Insert also: fail(, ) ←
not fail(, ), lit(, , ).
The efect of that rule is to make any two L-stable models that correspond to diferent configurations of the variables incomparable w.r.t. undefinedness. Then encode each clause = 1 ∨ 2 ∨ 3 by a set of rules cl(1, 2, 3) ← lit(, , ) and facts cl(1, 2, 3), as follows. If is a literal over a variable or , then add the corresponding atom lit(, , ) in the body and instantiate the logical variable to the respective constant x or y. If instead is over a variable, then select the respective logic variable to the constant 1 or 0, dependening of the assignment that satisfies the clause. For example, the clause ¬1 ∨ 1 ∨ ¬2 is encoded as cl(, 1, 2) ←
lit(, 1, 0). cl(, 1, 2). cl(1, 1, 0).
The formula is represented as the rule phi ← cl1(11, 12, 13), . . . , cl(1, 2, 3), where the variables are selected to reeflct the variables in literal mentioned in clause (if it is an / variable with use the constant /). Consider a configuration , to the variables and , and a corresponding t/finterpretation , of the groundings of lit(, , ). Then ∃ (, ) is true if an only if phi is satisfied by the extension of ,. Finally, insert the rule ← not , phi. The efect of that rule is to encode the universal quantification of variables . To see this, fix a configuration of the variables. Suppose there is a configuration such that ∃ (, ) is false. Then there is an L-stable model that defines phi (as false), defines values for all groundings of lit(, , ), and defines as false. Suppose instead that there is no such . Then for any model satisfying phi the atom must be undefined. Hence, there is an L-stable model satisfying phi only if Φ is true. To observe the converse, note that changing the interpretation of any atom either violates some clause or breaks minimality. Thus, checking if an L-stable model satisfies phi solves the 3-QBF problem.
We now handle the case with disjunctive rules.
Theorem 2. Deciding if there is an L-stable model satisfying a given atom for a disjunctive program with bounded-arity predicates is Σ 4-hard.
Proof. Hardness follows from a reduction from 4-QBF: ∃1, . . . , ∀1, . . . , ∃1, . . . , ∀1, . . . , . We repeat the same encoding in the proof of Theorem 1, with the following diferences. First, we encode ¬ as where cl(1, 2, 3) is the negation of the the -th clause. We also add phi ← not negphi, for convenience. We represent the literals relative to the variables as lit(, , ), and use the saturation technique to quantify over them: lit(, , 1) ∨ lit(, , 0). lit(, , ) ←
The existence of a configuration for which (, , , ) is false for some is represented by an interpretation defining both lit(, , 1) and lit(, , 0) as true, for = 1, . . . , . Since such an interpretation is ⊆ -dominated by any interpretation that assigns true to only one of the literals lit(, , ) (and false to the other), it is a model only if ∀ ∃ ¬(, ). The remainder of the proof is as in Theorem 1. 4. Complexity of Probabilistic Logic
Programs
If logical inference in some logic programming language
belongs to complexity class , then probabilistic inference
under the credal semantics in the corresponding
probabilistic logic programming language belongs to PPC [
Corollary 2. Probabilistic inference in propositional disjunctive programs under the credal L-stable semantics predicates is PPΣ 3 -complete.
Corollary 3. Probabilistic inference in normal probabilistic programs with bounded-arity predicates under the credal Lstable semantics is PPΣ 3 -complete.
Corollary 4. Probabilistic inference in disjunctive probabilistic programs with bounded-arity predicates under the credal L-stable semantics is PPΣ 4 -complete.
The argument however does not apply for the MaxEnt semantics. Intuitively, this is because that semantics has no inner decision problem, hence it is not clear how to relate the complexity of logical inference to the respective probabilistic inference complexity. In the rest of this section, we provide a few results regarding the complexity of MaxEnt semantics. As will become clear, such a semantics demands more sophisticated strategies.
We start by proving complexity of the restricted case
where the L-stable models in models( ) for any total
choice can be eficiently enumerated. This is the case, for
example, when the number of negated atoms, the number
of rules with non-empty bodies is limited or yet the size
of the strongly connected components of the dependency
graph are bounded [
Theorem 3. Deciding whether the probability of an atom exceeds a given threshold under the MaxEnt semantics for propositional disjunctive programs is PP-complete when the L-stable models of any induced logic program are eficiently enumerated.
Proof. Hardness follows from the complexity of stratified programs (where the number of induced stable models is 1).
Membership: We want to decide if Pr() ≥ for some program , atom and rational threshold . For simplicity we first assume that each total choice has uniform probability and that = 0.5. We later discuss how to generalize those assumptions.
Guess a total choice and let be an upper bound on |models( )|. To be able to eficiently enumerate models, needs to be polynomial on the input size. And since we can eficiently enumerate, we can also eficiently count both = |models( )| and the number of such models that satisfy . Thus guess a model in models( ) and branch the respective computation path into ! paths; for (!/ ) · of them accept the computation and for the (!/ ) · ¬ remaining, reject it. Let denote the number of total choices. The machine accepts with probability ∑︀⊆ facts( )(!/ ) · ∑︀⊆ facts( ) ! =
∑︁ ⊆ facts( )
Pr( ) , which equals Pr(). To lift the assumption of = 0.5, branch any accepting path such that it accepts with probability 0.5 + (1 − ) and branch any rejecting path such that it accepts with probability 0.5 − . Then we accept with probability Pr()· [0.5+(1− )]+[1− Pr()](0.5− ) = 0.5 + Pr() − , which is greater than 0.5 if Pr() > . To remove the assumption of uniform total choice probabilities, proceed as follows. For each atom ∈ with rational probability () = /, branch into paths: for of them insert into the logic program then proceed as before; for the remaining − do not insert and also proceed as before. Then a total choice is selected with probability Pr( ), and the machine accepts with probability ∑︀∈facts( ) Pr( ) / = Pr().
We now consider the more general case, that is, when model enumeration is not tractable.
Theorem 4. Deciding if the probability of an atom exceeds
a given threshold under the MaxEnt semantics for disjunctive
programs with bounded-arity predicates is in PPPP.
Proof. Denote by = |atoms( )| the number of
probabilistic facts and take = |atoms( )| − (for the grounded
program). Assume w.l.o.g. that the threshold is 0.5, and
that Pr( ) = 1/2 for all . Guess a total choice and
use the PP oracle to obtain the counts and ; note that
PPΣ ⊆ PPP for any > 0 [
While we conjecture that inference under the MaxEnt semantics is PPPP-complete, we have not yet been able to prove so. We can however show evidence that MaxEnt inference is at least as hard as inference under the credal semantics. Recall that, under the credal semantics, inference for propositional probabilistic normal logic programs whose stable models are all total (i.e., no atom is assigned undefined) is PPNP-complete. The following theorem shows that for those programs, MaxEnt inference is at least as hard.
Theorem 5. Deciding if the probability of an atom exceeds a given threshold under the MaxEnt semantics for propositional normal programs is PPNP-hard, even if all atoms are defined. Proof. We reduce from PPNP-complete problem MAJ-E-SAT, which consists of deciding if for the majority of configurations of a set of Boolean variables 1, . . . , there is a configuration of Boolean variables 1, . . . , that satisfy a given CNF formula (1, . . . , ). More formally, for each configuration = 1, . . . , let () denote the number of configurations of 1, . . . , such that (1, . . . , , 1, . . . , ) is true. The MAJ-E-SAT problem is to determine if
= ⃒⃒ { ∈ {0, 1} : () ̸= 0}⃒⃒ > 2− 1.
Let be the number of clauses in , and be the number of literals in the -th clause. We represent each literal in by an atom lit(, , ), where ∈ {x, y} indicates the set of variables to which the literal belongs, is the respective variable index in that set and ∈ {0, 1} indicates the signal (if negated or not). We define an operator (, ) that returns the atom lit(, , ) corresponding to the th literal in the th clause of . For example, if is (1 ∨ ¬2 ∨ 1) ∧ (¬1), then (1, 3) = lit(y, 1, 1) and (2, 1) = lit(x, 1, 0). Thus assemble the program:
Fix a total choice , hence a semantics for lit(x, 1, 0), . . . , lit(x, , 1). The mutual negative dependency of lit(y, , 1) on lit(y, , 0) and vice-versa, makes so that we potentially have one stable model for each of the 2 configurations of 1, . . . , . The atom phi is true in any such stable model if is satisfied by the corresponding configuration of and . Now let be some integer that we will soon define and extend that program with the following rules: aux(, 1) ← aux(, 0) ← phi, not aux(, 0). phi, not aux(, 1). The new program has 2 stable models for each stable model of the previous program that satisfies phi, and it has one stable model for each stable model of the previous program that does not satisfy phi. Thus, each corresponds to a total choice , and we have that = 2 · ()+(2 − ()). It follows that
Pr(phi) = 1 ∑︁ 2 · () 2 ∈0,1 2 · () + (︀ 2 − ())︀ .
Recall that our intention is to use Pr(phi) to decide if , the number of configurations for which () is nonzero, is greater than 2− 1. To this end, let = − 2 Pr() be the error introduced by our reduction. Note that since is an integer then either ≥ 2− 1 + 1 or ≤ 2− 1. Hence, if < 1, we can use the value of Pr(phi) to decide the MAJE-SAT problem. That error is maximized when () = 1 for each of the 2 configurations , hence: ≤ 2 −
2+ 2 + (2 − 1)
< 1 ⇔ 2 > (2 − 1)(2 − 1).
Thus, selecting = + ensures that < 1. To conclude, if Pr() > 1/2 we decide that MAJ-E-SAT is true, otherwise we decide that it is false.
Inference under the credal semantics is also PPNP-hard for propositional probabilistic disjunctive programs with no negation (which always admit a total stabel model). The next result shows that the same lower complexity is obtained for the MaxEnt semantics.
Theorem 6. Deciding if the probability of an atom exceeds a given threshold under the MaxEnt semantics for propositional disjunctive programs without negation is PPNP-hard. Proof. Again, we reduce from MAJ-E-SAT with a CNF formula . Assemble the program: clause(i) ← ′(, 1), . . . , ′(, ). The operator ′(, ) above returns the atom lit(, , ) corresponding to the negation of the th literal in the th clause of . For example, if is 1 ∨ ¬2 ∨ 1, then ′(1, 1) = lit(x, 1, 0).
Compared to the program in the proof of Theorem 5, the program above replaces negative cycles by disjunctions, and represents the negation of by the atom negphi. It also adds rules to employ the saturation technique. The efect is as follows. For a fixed total choice , that fixes the semantics of lit(x, , 1) for = 1, . . . , , there is not a congfiuration 1, . . . , that satisfies (, ) if the (single) stable model satisfies negphi. This is because such a model is saturated: lfipping the interpretation of any atom from true to false must cease being a model, else the model would not be minimal (as it assigns all atoms lit(y, , 0/1) to true). Hence, 2 Pr(phi) counts the number of assignments for which () > 0.
To benefit from state-of-the-art ASP solvers that adopt (total)
stable model semantics, we revisit a translation developed in
[
Example 7. Take the program in Example 2. Its translation is then the program
∨ . ∨ . ← ← not . ← not . ← not . ← not . ← . .
Table 3 shows interpretation (, , , ) and the respective program reducts their minimal models. To save space, we only list interpretations that satisfy rules ′ = { ∨ . ∨ . ← . ← }, as these are always in the reduct (and thus must be satisfied by any model). The interpretations in bold show the (total) stable models (which are also L-stable). The partial stable models of the original program are obtained by verifying whether atoms and disagree on the model.
← not . ← not . ← , not .
The first two rules enforce that in any stable model we either have both and undefined or both defined as diferent values. The third rule causes to be undefined if is true, and false when is false (so can be seen as the “enabler” of the rule). Thus, the only L-stable model is () = () = 0 and () = 1. The translation of the program is ← ← ← not . ←
As a proof of concept, we have implemented an inference
algorithm based on the described translation in the dPASP
system, available at http://github.com/kamel-usp/dpasp.
Our implementation work as follows. Given a probabilistic
logic program and a target atom, we obtain a new program
with the inclusion of the auxiliary variables. Then we
enumerate the total choices. For each total choice, we call clingo
[
As the program has only one L-stable model for each total choice, the credal and MaxEnt semantics coincide. The following table compares the probability of smokes(X) being undefined for each person, under the L-stable and smProblog semantics.
smProbLog
L-stable
One notes that the smProblog semantics assigns a lower probability mass to undefined states due to the allowing only one model with undefined atoms per total choice when faced with inconsistencies, while the L-stable semantics admits several and thus sums over all possible undefined models. In contrast, the L-stable semantics diferentiates the diferent degrees to which atoms are involved in inconsistencies.
Much more can be said about algorithms for inference
under the L-stable semantics. For example, to make the
procedure less ineficient, we can employ any of the many
approximate strategies from the probabilistic answer set
solving literature, such as searching for stable models
according to the their relative probability [
The L-stable semantics provides a very convenient treatment for expressing knowledge with default negation (hence nonmonotonic reasoning), nondeterminism (multiple models), and local inconsistency. The last property is particular important for probabilistic extensions of logic programming, since an inconsistent program has typically no semantics.
In this work, we have examined the complexity of probabilistic disjunctive logic programs under the L-stable semantics, thus filling a number of gaps in the literature (both for programs without and with probabilities). We showed complexity results for programs without variables and with variables and bounded-arity predicates under the credal semantics (which provides set-valued probabilistic inferences). And we partially characterized the complexity of inference under the maximum entropy semantics. Despite most literature in probabilistic logic programming with multiple models being focused on the latter, there has been virtually no complexity analysis thus far, even in the absence of contradictions.
A few extensions to those results should be relatively easy to build based on the techniques presented here. For instance, inferences that concern the search for maximum probability models or probabilistic inferences when the program is fixed (i.e., data complexity) are likely to be obtained with much similar results. We leave that as future work.
This work leaves open a seemingly much harder question,
namely, how to close the gap between lower and upper
complexity for inference under the maximum entropy semantics.
Interestingly, the maximum entropy semantics might seem
at first to lead to counting problems with obvious counting
oracles; however, the “inner” counting of models does not
contain itself a decision problem — hence the need for the
more sophisticated proofs we had to build. We presented
her an upper bound that shows that inference in that
semantics is at most PPPP. That complexity reduces to PP, for
programs whose intended models are eficiently
enumerable. And we showed that the inference is already PPNP-hard
in propositional programs with no contradictions and that
have either no negation or no disjunction, thus matching
the complexity of credal semantics [
The authors of this work would like to thank the generous support from the Center for Artificial Intelligence at University of São Paulo (C4AI-USP), the São Paulo Research Foundation (FAPESP grants #2019/07665-4 and 2022/029379), the IBM Corporation, the Brazilian National Research Council (CNPq grants no. 305136/2022-4 and 305753/2022-3) and from CAPES (Finance Code 001).