Various probabilistic description logics (DLs) have been proposed for dealing with the uncertainty endemic to many domain knowledge representation scenarios. A particular class of such formalisms focuses on representing knowledge that is certain, but holds only in some uncertain contexts. In this paper, we consider an extension of those formalisms that allows an agent to in uence the choice of the context and minimise its subjective cost. This is achieved through a combination of the light-weight DL EL and in uence diagrams, a graphical model for representing decision situations, and their potential costs, under uncertainty.
A well-recognised limitation of classical description logics (DLs) [
The expressive power of Bayesian DL arises from combining a set of
(classical) DL ontologies (called contexts) with a Bayesian network (BN) [15]
representing the joint probability distribution of these ontologies to hold. This allows
to reason about the likelihood of a consequence to hold, but also update the
beliefs about the probabilities of the contexts. However, this remains as a
passive attitude towards knowledge. In practice, one would like an agent to be
able to make choices depending on its knowledge and observations. Some earlier
works [
In uence diagrams (IDs) [17] are a generalisation of BNs aimed at modelling
potential decisions made by an agent and their associated cost. As a typical toy
example, an agent has to decide whether to go for a picnic or not, based on the
weather forecast that depends (unreliably) on the actual weather. The overall
cost to the agent will depend on their choice and on the state of the weather (see
Figure 1). In this paper we propose an extension of the Bayesian DL BEL [7] to
allow for agent decisions combining in uence diagrams with the light-weight DL
EL [
In ID-EL, the contexts consider the uncertainty in the network, as well as the potential choices from the agent and, obviously, also their associated cost. More importantly, the ontological knowledge can be used as evidence about the potential context, thus modifying the underlying probabilities. We study the reasoning problems associated with the selection, by the agent, of a strategy that minimises its expected cost given such evidence. 2
In uence diagrams (IDs) [17] are a generalisation of Bayesian networks (BNs) [15], which contain three types of nodes: chance nodes that re ect the uncertainty of the environment as in BNs; decision nodes, which express the choices made by an agent in response to the environment; and a cost node (sometimes also called a utility node), which re ects the cost (or utility) of a given outcome. From a formal perspective, each of these nodes represents a discrete random variable, and the main di erence is how this variable is interpreted or used within the network.
Formally, an in uence diagram is a pair D = (G; ) where G = (V [ fcg; E) is a directed acyclic graph (DAG), whose nodes V are partitioned into two sets B and D of chance nodes (or Bayesian nodes ), and decision nodes, respectively, and c is a single cost node. For simplicity, we assume w.l.o.g. that all nodes in V are Boolean random variables.4 The cost node c has no outgoing edges, and represents a cost function from the valuations of its parent nodes to a nite set val(c) R of values. For every node v 2 V [ fcg, (v) denotes the parents of v. Given a decision node d 2 D, d-anc(d) is the set of all decision ancestors of d, and
in (d) := d-anc(d) [ (d): is the in uence set of d. When the set of nodes in D is V [fcg, we say that D is an ID over V . The second part of the tuple D, , is a class of conditional probability distribution tables P (v j (v)), one for each chance node v 2 B given its parents. Notice that there is no probability distribution associated with decision nodes, and recall that the node c represents a function from the class of all valuations of (c) to R.
IDs are represented graphically using circles to denote chance nodes, squares for decision nodes, and a diamond for the cost node; see Figure 1. Seen in this 4 In general, chance and decision nodes can be arbitrary nite random variables. By considering only the Boolean case, we greatly simplify the notation and presentation, without a ecting the generality of the approach.
x 0.7 x y c x 0.7 :x 0.5
c x z 20 x :z 8 :x z 0 :x :z 20 z
y :y z way, an ID can be thought of as an incomplete BN where some of the nodes are missing their conditional probability tables, given their parents.5
If these tables are added to the ID, then one could derive the joint probability distribution of all the variables in V using the standard chain rule from BNs PD(V ) =
Y P (v j (v)): v2V Instead, in an ID, the decision nodes correspond to choices that an agent can make based on the information available. The actual response of the agent is called a strategy.
De nition 1 (Strategy). A (local) strategy on a decision node d 2 D is a conditional probability distribution of d given its in uence set in (d). A (global) strategy on the ID D is a set of local strategies, containing one for each d 2 D. A local or global strategy is pure if it only assigns probabilities 0 or 1. Note that the strategy at a decision node does not depend on its parents only, but on its whole in uence set; that is, it depends on its decision ancestors. Intuitively, we can see the direction of the DAG as a precedence in the choices made. Hence, every decision depends also on the choices made earlier. This can be seen as having implicit connections between the node d and its in uence set. This assumption, known as no-forgetting, is commonly used in IDs, thus we include it in our formalism. However, removing it would have no e ect over the results in this work. In the ID from Figure 1, one possible pure strategy would be to assign P (z j :y) = P (:z j y) = 1. To distinguish pure and general 5 Note that the utility function can be seen as a special kind of probability distribution over the set val(c), where probabilities are always 0 or 1. strategies, we often call the former an action. We denote by PD(S) the probability distribution obtained by adopting the strategy S in D.
Clearly, an agent has a large class of strategies from which to choose. Which one is better depends on the probability of paying di erent costs given the chosen strategy. One usual approach is to try to minimise the expected cost. De nition 2 (Expected cost). Given a global strategy S on the ID D, the expected cost of S w.r.t. D is
E[D j S] :=
X r2val(c) r PD(S)(c = r): For example, if we use the aforementioned strategy S in the ID D from Figure 1, we obtain that
PD(S) = 8>0:15 r = 0 <
0:49 r = 8 >:0:36 r = 20: Hence, expected cost E[D j S] = 0 0:15 + 8 0:49 + 20 0:36 = 11:12.
As mentioned, strategies in IDs are often targeted to minimising the expected cost on the resulting network. However, other kinds of problems can also be considered over such a network, such as nding the most likely cost, or maximising the probability of the minimum cost. If we limit ourselves to pure strategies only, then one can verify that the strategy S in our running example is in fact the one which minimises the expected cost. On the other hand, the strategy S0 which assigns P (z j y) = P (z j :y) = 1 maximises the probability of observing the least possible cost 0: PD(S0)(c = 0) = 0:3.
In the next section, we propose a combination of IDs with the description logic EL and later study some of its reasoning problems. 3
We now introduce a new logic that combines the light-weight DL EL with an inuence diagram to allow reasoning and deriving strategies according to observed knowledge. The connection between the two formalisms is based on adding a contextual annotation to every axiom, expressing in which circumstances it is required to hold. We formalise this next.
De nition 3 (KB). Consider a nite set V of contextual variables (or variables for short) and two disjoint sets NC and NR or concept and role names, also disjoint with V . ID-EL concepts are constructed through the grammar rule C ::= A j > j C u C j 9r:C, where A 2 NC and r 2 NR. A (contextual) general concept inclusion (V -GCI) is an expression of the form hC v D : 'i where C; D are two ID-EL concepts and ' is a propositional formula over V . A V -TBox is a nite set of V -GCIs. An ID-EL knowledge base (KB) is a pair K = (D; T ), where D is an ID over V and T is a V -TBox.
As with other context-based DLs introduced in the past [5, 9], the idea is that a V -GCI is only required to hold when its context ' is satis ed. This intuition is formalised via a possible world semantics that uses so-called V -interpretations. These combine classical DL interpretations with propositional valuations to link the GCIs with their contexts.
De nition 4 (Semantics). A V -interpretation is a triple I = ( I ; I ; VI ), where I is a non-empty set called the domain, VI : V ! f0; 1g is a valuation of V , and I is the interpretation function that maps every A 2 NC to a set AI I and every r 2 NR to a binary relation rI I I . This function is extended to complex concepts as usual in EL.
The V -interpretation I satis es the V -GCI hC v D : 'i (I j= hC v D : 'i) i VI 6j= ' or CI DI . It is a model of the V -TBox T i it satis es all V -GCIs in T .
When there is no ambiguity, we omit the pre x V and speak of e.g., interpretations or TBoxes.
Clearly, the probabilistic DL BEL [9]|which combines a contextual ontology with a Bayesian network|is a special case of ID-EL, where there are no decision nodes, and the cost node is ignored (e.g., it may be disconnected from the rest of the DAG). As in that special case, it is often useful to consider the classical EL TBox induced by a valuation of the variables in V.
De nition 5 (Restricted KB). Let K = (D; T ) be a KB, and W a valuation of the variables in V . The restriction of T to W is the EL TBox
TW := fC v D j hC v D : 'i 2 T ; W j= 'g: To consider the uncertainty associated with the contexts, BEL de nes a possible world semantics where each world is associated with a probability that needs to be compatible with the probability distribution of the nodes. In ID-EL this de nition cannot be applied directly, because the actual probability distribution is underspeci ed, and depends on the strategy chosen by the agent. Thus, we consider probabilistic models that are parameterised w.r.t. a strategy. De nition 6 (Probabilistic model). A probabilistic interpretation is a pair P = (I; PI), where I is a nite set of V -interpretations and PI is a probability distribution over I. This probabilistic interpretation is a model of the TBox T if every I 2 I is a model of T .
Given an ID D and a strategy S on D, the probabilistic interpretation P is consistent with D w.r.t. S if for every possible valuation W of the variables in V it holds that PD(S)(W) = PI2I;VI=W PI(I).
P is a model of the KB K = (D; T ) w.r.t. the strategy S (denoted as P j=S K) i it is a model of T and consistent with D w.r.t. S.
Example 7. Let Kexa = (D; Texa) be the ID-EL KB where D is the ID in Figure 1, and
Texa := fhA v B : :x _ zi; hB v C : :z _ xi; hB v D : :x ^ zig: B; D
A; B; C fx; y; zg fx; :y; :zg f:x; y; zg f:x; :y; :zg One possiblevaluation of the variables in V is Wexa = f:x; y; :zg. The interpretation Iexa = (f g; eIxa; Wexa) where AeIxa = BeIxa = f g and CeIxa = DeIxa = ; satis es the rst and the last GCIs, but not of the second.
Consider now the interpretations Ii := (f g; Ii ; Wi); 1 i 4, where AI1 = f g AI2 = ; AI3 = ; AI4 = f g
BI1 = f g BI2 = ; BI3 = f g BI4 = f g
CI1 = f g CI2 = ; CI3 = ; CI4 = f g
DI1 = f g DI2 = ; DI3 = f g DI4 = ; and W1 = fx; y; zg, W2 = fx; :y; :zg, W3 = f:x; y; zg, W4 = f:x; :y; :zg, depicted in Figure 2. It is easy to verify that the probabilistic interpretation Pexa = (I; PI) with I = fI1; : : : ; I4g and PI1 = 0:49, PI2 = 0:21, PI3 = 0:15, PI4 = 0:15 is a model of Texa and is consistent with the strategy S that assigns P (z j :y) = P (:z j y) = 1. Hence Pexa is a model of Kexa w.r.t. S. We emphasise once more that the notion of a model is always dependent on a given strategy chosen by the agent. This is in line with our understanding of IDs. For instance, the strategy of an agent could be such that some contexts become impossible. Then, a model of the knowledge of this agent should disallow to have those contexts with any positive probability. As a consequence, the basic reasoning tasks in ID-EL must also be parameterised on the chosen strategy. We also note that the requirement for I to be nite can be relaxed by imposing some additional constraints in the probability distribution PI. To avoid unnecessary technicalities, we simply focus on the nite case.
We can now de ne the cost associated with V -interpretations and probabilistic models.
De nition 8 (Expected cost). Given an ID D over V, the cost of the V -interpretation I = ( I ; I ; VI ) is c(I) := c(VI j (c)), where VI j (c) denotes the restriction of the valuation VI to the parents of c.
Given a strategy S on D and a probabilistic interpretation P = (I; PI) which is consistent with D w.r.t. S, the expected cost of P (w.r.t. S) is E[P j S] :=
X PI(I) c(I):
I2I Since the probability distribution in a probabilistic model must be consistent with the distribution induced by the strategy S, the expected cost of any model of a KB K = (D; T ) w.r.t. S corresponds exactly to the expected cost of D w.r.t. S. That is, once that the strategy has been chosen, the expected cost does not depend on the speci c model of K. Thus, we can de ne the expected cost of K w.r.t. S as E[K j S] := E[P j S], where P is any model of K.
Rather than de ning a cost function directly on the nodes of the network, it sometimes makes sense to consider this function to be implicitly de ned by the properties of the contexts that the node c can observe. In the extreme case, all nodes in V are parents of c and de ning the cost function in terms of the contexts obtained by each valuation avoids having to represent the exponentially large mapping. A natural choice for such a cost function is the size of the context. Intuitively, this function allows us to express that a smaller context is preferred over a larger one. Using this function makes sense, for instance, when the context needs to be transferred or manipulated over an unreliable channel. A smaller ontology is preferred to reduce the risk of errors. However, many other functions can be considered depending on the application. As an additional example, if the contexts refer to di erent levels of granularity of access, then considering the size of the vocabulary as cost is more relevant. We emphasise, however, that ID-EL does not require the use of any of these cost functions, or even that the node c is in uenced by all nodes in V. These are just given as concrete examples with an application-oriented motivation. 4
Before delving in detail into the reasoning tasks for ID-EL, we notice that just as in the special cases of EL and BEL, every ID-EL ontology is consistent. More precisely, for every ID-EL KB and strategy S, there is a model of K w.r.t. S. Hence, we are more interested in reasoning problems related to subsumptions, their probabilities, and more importantly, their costs.
The rst reasoning task that we consider in this setting corresponds to computing bounds on the expected costs associated with the models of a given KB K. That is, we would like to compute an optimal strategy, which minimises the expected cost w.r.t. D, and a pessimal strategy, which maximises this cost. From the previous discussion, it follows that these bounds correspond exactly to the bounds on the expected cost of the ID D from K. To speak about complexity, we consider their associated decision problem versions.
Problem 9 (Optimal/Pessimal strategy). Given an ID D and b 2 R, the optimal strategy problem (D-Opt) is to decide whether there is a strategy S such that E[D j S] < b. Dually, the pessimal strategy problem (D-Pes) is to decide whether there is a strategy S such that E[D j S] > b.
Both of these problems are PSpace-complete [12]. It follows that the analogous problems de ned for ID-EL KBs are PSpace-complete as well.
Theorem 10. Given an ID-EL KB K = (D; T ) and b 2 R, deciding whether there exists a strategy S such that E[K j S] < b or E[K j S] > b is PSpacecomplete.
Notice, however, that in general we cannot expect a polynomial-space algorithm to enumerate an optimal strategy. Indeed, even if we limit the search to pure strategies, we should observe that a pure local strategy is merely a Boolean function over the parent variables. It is well known that for every n 2 there exist Boolean functions (and hence, local strategies) that cannot be expressed with circuits of size smaller or equal to 2n=2n [18].
One can also consider the problem of entailment of a contextual subsumption, or computing the probability of a subsumption relation to hold. For the latter, as already explained, one must rst instantiate the chosen strategy. De nition 11 (Probabilistic subsumption). Let K = (D; T ) be a KB, a context, and C; D two ID-EL concepts. Given the probabilistic interpretation P = (I; PI), the probability of hC v D : i w.r.t. P and w.r.t. the strategy S over D are de ned, respectively, as
P (hC vP D : i) := P (hC vK;S D : i) :=
X
PI(I); I2I;Ij=hCvD: i
inf P (hC vP D : i): Pj=SK and In particular, we denote as P (C vP D) the case where = true is the universal context satis ed by all propositional valuations.
Recall that an ID together with a strategy forms a BN, and hence after choosing the strategy, the probability of each instantiation of all the variables in V is fully speci ed. Still, one can choose di erent models for the KB w.r.t. this strategy. Indeed, note that the universal EL model which contains only one element belonging to all concepts and connected to itself via all roles, can always be used to build a probabilistic model P such that P (hC vP D : i) = 1 for all concepts C; D. Choosing the in mum in the de nition of the probability of a subsumption is the natural cautious bound that is guaranteed to hold in all models.
In a decision situation, an agent might observe a fact, and try to act upon it with the best available strategy. In IDs, this is modelled through the introduction of evidence; formally, the instantiation of one of the chance nodes. In our setting, we are more interested in observing facts that arise from the ontological perspective. Hence, rather than observing the behaviour of the ID, we observe a fact that provides information about the possible contexts that can still hold, hence also in uencing the probability distribution over the underlying ID. In practice, when we observe a consequence, we can immediately exclude some cases which contradict our observation. The probabilities of the remaining cases need to be updated accordingly.
De nition 12 (Conditional expected cost). Let K = (D; T ) be an ID-EL KB, S a strategy on D, P = (I; PI) a probabilistic model of D w.r.t. S, and C; D two concepts such that P (C vP D) > 0. The conditional probability of the interpretation I 2 I given the subsumption C v D is
PI(I j C v D) := (0
PI(I) P (CvP D) if I 6j= C v D otherwise.
The conditional expected cost of P given C v D w.r.t. S is
E[P j S; C v D] :=
X PI(I j C v D) c(I):
I2I As when dealing with probabilities alone, when trying to understand the expected cost given an observation it is important to consider all the possible models of the KB. Accordingly, we can consider an optimistic or a pessimistic approach depending on whether we try to maximise or minimise this expected cost.
De nition 13. Let K be an ID-EL KB, S a strategy, and C; D two concepts. The optimistic expected cost E and the pessimistic expected cost E of K w.r.t. S given C v D are de ned, respectively, by
E[K j S; C v D] := E[K j S; C v D] :=
inf E[P j S; C v D]; Pj=SK sup E[P j S; C v D]:
Pj=SK Note that, as mentioned already, for every context it is always possible to construct an EL model of the context that satis es also the GCI C v D. In such a model P = (I; PI), it always holds that PI(I j C v D) = PI(I) for all I 2 I. In particular, this also means that E[P j S; C v D] = E[P j S] for all strategies S. This yields the following result.
Proposition 14. For every ID-EL KB K, strategy S, and concepts C; D, it holds that E[K j S; C v D] E[K j S] E[K j S; C v D].
Example 15. Consider again the KB Kexa from Example 7. We have already seen that under the pure strategy P (z j :y) = P (:z j y) = 1, it holds that E[Kexa j S] = 11:12. Consider now the evidence A v C. It is easy to see that there exists a probabilistic model P such that E[P j S; A v C] = 20. Similarly, if the evidence is A v D, there is a model P0 such that E[P0 j S; A v D] = 0. Hence, in general the pessimistic and optimistic expected costs given an evidence do not coincide with the expected cost of the KB. This example also shows that di erent models may reduce or increase the expected cost, in manners that may not be obvious at rst sight.
Theorem 16. Optimistic and pessimistic expected costs given C v D can be computed in polynomial space on the size of V .
Proof. There are exponentially many valuations of the variables in V . For each valuation W, we construct the TBox TW . Let n be the smallest value in val(c). We construct a probabilistic model P = (I; PI) as follows. For each valuation W, I contains a V -interpretation IW = ( IW ; IW ; W) s.t. (i) ( IW ; IW ) j= TW , (ii) if c(I) = n then ( IW ; IW ) j= C v D, and (iii) if c(I) 6= n and TW 6j= C v D, then ( IW ; IW ) 6j= C v D. Moreover, PI(IW ) = PD(S)(W). It is easy to verify that this is a model, constructed in exponential time, and minimises the expected cost. To compute this cost in polynomial space, we store only one interpretation at a time, and accumulate the relative cost of each interpretation iteratively. For the pessimistic expected cost, the proof is analogous. tu However, we are not interested in the expected costs per se, but rather as a means to identify the best strategy that the agent can follow under the evidence. In this case, we have the choices to minimise or maximise the optimistic or pessimistic expected costs, which yields four di erent notions. To reduce the overhead of the de nition, we focus only on minimising these costs; notice however that maximisation can be treated analogously.
De nition 17 (Dominant strategies). Let K be an ID-EL KB and C; D two concepts. The strategy S is dominant optimistic if for every strategy S0 it holds that E[K j S; C v D] E[K j S0; C v D]. It is dominant pessimistic if for all strategies S0, E[K j S; C v D] E[K j S0; C v D].
A nave approach for nding pure dominant strategies is to enumerate all possible options, and preserve those that yield the lowest expected costs. In the worst case, there are doubly-exponentially many such strategies on the size of V , which makes this nave approach infeasible, despite its e ectiveness. On the other hand, it is easy to see that the optimal strategy for the whole network is a special case of De nition 17, where C v D corresponds to any EL tautology (e.g., A v A).
Consider the decision problems (D-Dom-Opt and D-Dom-Pes, respectively) associated with De nition 17: given a KB K, two concepts C; D and b 2 R, decide whether there are strategies S; S0 such that E[K j S; C v D] < b, and E[K j S0; C v D] < b, respectively. Using an approach similar to Theorem 16, we can build a polynomial-space algorithm for deciding D-Dom-Opt under pure strategies by enumerating all valuations of the chance nodes, guessing for each of them a valuation of the decision variables and computing the minimal cost that arises from each of them. The only issue is that this needs to be done in a speci c order to guarantee that for equal parent nodes, the same guess is made always in a decision variable.
Theorem 18. The problems D-Dom-Opt and D-Dom-Pes are PSpace-complete for pure strategies.
Obviously, the lower bound holds also for arbitrary strategies. The upper bound can be extended to non-pure strategies, as long as they are representable in exponential space; otherwise, we would not be able to guess them in exponential time.
We have introduced ID-EL, a new extension of the DL EL capable of modeling and dealing with decision situations under uncertainty. This is achieved by integrating an in uence diagram to represent the uncertainty, potential decisions, and the overall costs of a choice. The ontological (EL) portion and the in uence representation are combined through contexts. From an abstract point of view, we build a collection of ontologies, which hold only in speci c contexts. These ontologies contain only certain knowledge, but the speci c context under consideration is uncertain.
Extending the basic idea of BEL, our framework allows for an agent to in uence its context by making choices in speci c nodes of the network. The agent is motivated to make choices that minimise the overall expected cost. Intuitively, this means minimising the probability of large costs, and maximising the probability of low costs.
We studied the basic reasoning problems in this logic, and gave tight complexity bounds for all of them. Interestingly, the decision problem associated with nding a dominating optimal strategy, in which the agent should nd the best strategy conditioned on an ontological observation, remains PSpace-complete. A practical algorithm for solving this problem is left for future work. As future work we will also consider other decision-based reasoning tasks, and complexity classes. Notably, we will study whether optimal strategies or costs can be approximated e ciently. Moreover, we will consider the task of building strategies iteratively, as a response to the environment; this is justi ed by the no-forgetting assumption of IDs. Another interesting issue to resolve is how to dislodge the strategies from the underlying ID, and allow the agent to select consequences (rather than direct contexts) instead.
To conclude, we note that the choice of EL as a logical formalism is motivated by its polynomial-time reasoning problems, which allow us to understand complexity issues better. However, our framework can be combined with other (potentially more expressive) logics. Building those extensions introduces further problems (e.g., consistency) that would need to be studied in detail as well. 5. Baader, F., Knechtel, M., Pen~aloza, R.: Context-dependent views to axioms and consequences of semantic web ontologies. Journal of Web Semantics 12, 22{40 (2012). https://doi.org/10.1016/j.websem.2011.11.006 6. Botha, L., Meyer, T., Pen~aloza, R.: A Bayesian extension of the description logic ALC. In: Proceedings of the 16th European Conference on Logics in Arti cial Intelligence (JELIA'19). Lecture Notes in Computer Science, vol. 11468, pp. 339{ 354. Springer (2019) 7. Ceylan, I_.I_., Pen~aloza, R.: The Bayesian description logic BEL. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) Proceedings of the 7th International Joint Conference on Automated Reasoning (IJCAR'14). Lecture Notes in Computer Science, vol. 8562, pp. 480{494. Springer (2014) 8. Ceylan, I_.I_., Pen~aloza, R.: Bayesian description logics. In: Proceedings of the 27th International Workshop on Description Logics (DL' 14). CEUR Workshop Proceedings, vol. 1193, pp. 447{458. CEUR-WS.org (2014), http://ceur-ws.org/Vol1193/paper 5.pdf 9. Ceylan, I_.I_., Pen~aloza, R.: The Bayesian ontology language BEL. Journal of Automated Reasoning 58(1), 67{95 (2017). https://doi.org/10.1007/s10817-016-9386-0 10. d'Amato, C., Fanizzi, N., Lukasiewicz, T.: Tractable reasoning with bayesian description logics. In: Greco, S., Lukasiewicz, T. (eds.) Proceedings of the Second International Conference on Scalable Uncertainty Management (SUM 2008). Lecture Notes in Computer Science, vol. 5291, pp. 146{159. Springer (2008). https://doi.org/10.1007/978-3-540-87993-0 13 11. Gutierrez-Basulto, V., Jung, J.C., Lutz, C., Schroder, L.: Probabilistic description logics for subjective uncertainty. Journal of Arti cial Intelligence Research 58, 1{66 (2017). https://doi.org/10.1613/jair.5222 12. Littman, M.L., Majercik, S.M., Pitassi, T.: Stochastic Boolean satis ability. Journal of Automated Reasoning 27(3), 251{296 (2001) 13. Lukasiewicz, T., Straccia, U.: Managing uncertainty and vagueness in description logics for the semantic web. Journal of Web Semantics 6(4), 291{308 (2008) 14. Niepert, M., Noessner, J., Stuckenschmidt, H.: Log-linear description logics. In:
Twenty-Second International Joint Conference on Arti cial Intelligence (2011) 15. Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible
Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1988) 16. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the distribution semantics. Semantic Web 6(5), 477{501 (2015) 17. Shachter, R.D.: Evaluating in uence diagrams. Operations Research 34(6), 871{ 882 (1986). https://doi.org/10.1287/opre.34.6.871 18. Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Technical Journal 28(1), 59{98 (1949). https://doi.org/10.1002/j.15387305.1949.tb03624.x