# Aleatoric Description Logic for Probabilistic Reasoning (Long Version)

Tim French
The University of Western Australia
<EMAIL_ADDRESS>Thomas Smoker
The University of Western Australia
<EMAIL_ADDRESS>
###### Abstract

Description logics are a powerful tool for describing ontological knowledge
bases. That is, they give a factual account of the world in terms of
individuals, concepts and relations. In the presence of uncertainty, such
factual accounts are not feasible, and a subjective or epistemic approach is
required. Aleatoric description logic models uncertainty in the world as
aleatoric events, by the roll of the dice, where an agent has subjective
beliefs about the bias of these dice. This provides a subjective Bayesian
description logic, where propositions and relations are assigned probabilities
according to what a rational agent would bet, given a configuration of
possible individuals and dice. Aleatoric description logic is shown to
generalise the description logic ALC, and can be seen to describe a
probability space of interpretations of a restriction of ALC where all roles
are functions. Several computational problems are considered and model-
checking and consistency checking algorithms are presented. Finally, aleatoric
description logic is shown to be able to model learning, where agents are able
to condition their beliefs on the bias of dice according to observations.

_Keywords_ Probabilistic Reasoning $\cdot$ Belief Representation $\cdot$
Learning Agents

##  1 Introduction

Description logics [1] give a formal foundation for ontological reasoning:
reasoning about factual aspects of the world. However, many reasoning tasks
are performed in the presence of incomplete or uncertain information, so a
reasoner must apply some kind of belief model to approximate the true state of
the world. This work investigates the application of description logics to
describing uncertain and incomplete concepts, following the recent development
of aleatoric modal logic [7]. The term aleatoric has its roots in the Latin
aleator, meaning dice player. and it is this origin that motivates this work.
Concepts are not simply described as matters of fact, but can be more
generally described as reasonable bets. While a person may definitely have a
virus or not, a virus test kit with 95% accuracy is effectively a role of a
dice, and often this aleatoric information is the only information available.
In the medical domain observed symptoms and anatomical structure may be
considered as fact, but diagnosis and prognosis have an inherent degree of
uncertainty. Therefore concepts may be modelled using probabilities
corresponding to a rational bet that the concept holds true, along the lines
of the Dutch book argument of Ramsey [23] and de Finetti [5].

The fundamental assumption of this work is that an agent models the world
aleatorically, where events correspond to the roll of dice, and the bias of
the dice is treated epistemically. That is, the agent has prior assumptions
about the bias of the dice, and may refine these assumptions through observing
the world.

Aleatoric description logic aims to model reasoning in uncertain and
subjective knowledge settings [10, 12]. However, aleatoric description logic
only offers a useful approximation of subjective reasoning, rather than an
ontic representation of reasoning that an actual agent may perform. Imagine a
rational agent that maintains an incomplete model of the world in their mind.
When the agent is asked to make a judgement, they simulate a complete
representation of the world by sampling the pertinent unknowns of the model,
applying likelihoods coherent with their past experience. The judgement that
is “most likely” becomes the position of the agent. There is a great variation
in the way such models could be formed, and sampled against. Aleatoric
description logic takes a pragmatic approach that assumes these models may be
represented by dice based games (often refer to as role playing games, such as
Advanced Dungeons and Dragons [9]), where intricate sets of dice determine the
unknowns of the model.

Aleatoric description logic takes an approach where the probabilistic and
logical aspects of the knowledge base are completely unified, rather than
several other approaches where these are independent facets of the knowledge
base [4, 26, 18]. Therefore all concept and roles are represented by “dice
rolls” corresponding to an agent’s beliefs on the likely configuration of the
world.

An advantage of this “probability first” approach is that aleatoric
description logic is naturally able to model learning via Bayesian
conditioning over complex observations (i.e. logical formula). Aleatoric modal
logic is introduced in [7], where the semantics are presented along with a
proof theoretic calculus. This paper extends that syntax and semantics to an
aleatoric description logic, following as an analogue of the correspondence
between description logics and modal logics [1]. Additionally: it will be
shown how the aleatoric semantics are actually a probability space of
functional models; knowledge base semantics are presented; satisfiability of
acyclic axiom schemas is shown to be in PSPACE; and finally a learning
framework will be presented where beliefs may be updated according to new
observations, via Bayesian conditioning.

##  2 Propositional description logic

Description logic gives mathematical description of that which is (i.e. things
that exist). The logical formalisation allows us to determine when two
concepts are equivalent, when one concept subsumes another, and when one
concept can be extended to include another.

There are many variations of description logic with different expressivity and
reasoning complexity 111http://www.cs.man.ac.uk/ ezolin/dl/, but we will focus
on the general purpose framework $\mathcal{ALC}$.

The syntax of complex concepts in $\mathcal{ALC}$ is is given by the following
recursion:

$C\ ::=\ \top\ |\ A\ |\ C\sqcap C\ |\ \lnot C\ |\ \exists\rho.C$

where $A\in\mathrm{X}$ is some atomic concept, and $\rho\in\mathrm{R}$ is a
role. This syntax enables the expression of complex concepts built from atomic
concepts.

######  Definition 2.1.

An interpretation of $\mathcal{ALC}$ is a tuple $\mathcal{I}=(I,c,r)$ where

  * •

$I$ is a set of individuals,

  * •

$c:\mathrm{X}\longrightarrow\wp(I)$,

  * •

$r:\mathrm{R}\longrightarrow\wp(I\times I)$,

The semantics of $\mathcal{ALC}$ are given with respect to a state $i\in I$
(the pointed interpretation ($\mathcal{I}_{i}$)) so that:
$\mathcal{I}_{i}\models\top$ always; $\mathcal{I}_{i}\models A$ iff $i\in
c(A)$; $\mathcal{I}_{i}\models C\sqcap D$ iff $\mathcal{I}_{i}\models C$ and
$\mathcal{I}_{i}\models D$; $\mathcal{I}_{i}\models\lnot C$ iff
$\mathcal{I}_{i}\not\models C$; and $\mathcal{I}_{i}\models\exists\rho.C$ iff
for some $j$ such that $(i,j)\in r(\rho)$, $\mathcal{I}_{j}\models C$.

The logic $\mathcal{ALC}_{1}$ is a particular semantic restriction of
$\mathcal{ALC}$ where the roles relation is constrained to be functional: i.e.
$\forall i\in I,\ \forall\rho\in\mathrm{R},\ |\\{j\ |\ (i,j)\in
r(\rho)\\}|=1$. The logic $\mathcal{ALC}_{1}$ is very basic and its concept
satisfiability problem has a linear reduction to propositional logic. However,
it provides an important foundation for the expressive relationship between
$\mathcal{ALC}$ and $\mathrm{ADL}$.

######  Lemma 2.2.

There is a computable linear transformation $\pi$ that maps
$\mathcal{ALC}_{1}$ to propositional logic, and a computable linear
transformation $\tau$ that maps interpretations of $\mathcal{ALC}_{1}$ to
interpretations of propositional logic such that for all pointed
interpretations $\mathcal{I}_{i}$ and all $\mathcal{ALC}$ formulas, $C$,
$\mathcal{I}_{i}\models C$ if and only if $\mathcal{I}_{i}^{\tau}\models
C^{\pi}$.

#### Proof:

For every word $w\in\mathrm{R}^{*}$, and for every concept $X\in\mathrm{X}$,
let $X_{w}$ be a propositional atom. For every word $w\in\mathrm{R}^{*}$, we
define a recursive transformation, $(\dot{)}^{w}$, from $\mathcal{ALC}_{1}$
formulas to propositional formulas as follows:

$\top^{w}=\top\quad(C\sqcap D)^{w}=C^{w}\land D^{w}\quad(\lnot C)^{w}=\lnot
D^{w}\quad\exists\rho.C=C^{\rho w}.$

Given a pointed $\mathcal{ALC}_{1}$ interpretation $\mathcal{I}_{i}=(I,c,r)$,
$\mathcal{I}_{i}^{\tau}$ is a subset of propositional atoms from $\\{X_{w}\ |\
w\in\mathrm{R}^{*},\ X\in\mathrm{X}\\}$, defined recursively as follows:

$\mathcal{I}_{i}^{\tau}=\\{X_{\epsilon}\ |\ i\in
c(X)\\}\cup\bigcup_{\rho\in\mathrm{R}}\\{X_{\rho w}\ |\ \exists j,\ (i,j)\in
r(rho),\ X_{\rho}\in\mathcal{I}_{j}^{\tau}\\}$

where $\epsilon$ is the empty word. It is straightforward to show
$\mathcal{I}_{i}\models C$ if and only if $\mathcal{I}_{i}^{\tau}\models
C^{\epsilon}$ by induction over the complexity of formulas. $\square$

##  3 Aleatoric description logic

This section presents the core syntax and semantics for Aleatoric Description
Logic ($\mathrm{ADL}$). This is a generalisation of standard description
logics, such as $\mathcal{ALC}$, in the same sense that complex arithmetic is
a generalisation of real-valued arithmetic: the true-false/0-1 values of
description logics are extended to the closed interval $[0,1]$.

###  3.1 Syntax

The syntax of $\mathrm{ADL}$ varies from that of $\mathcal{ALC}$ in a number
of ways: there is a ternary operator, if-then-else, in place of the typical
Boolean operators, and a marginalisation operator in place of the normal role
quantifiers. These operators add expressivity, but also better capture the
aleatoric intuitions of the logic.

The syntax for $\mathrm{ADL}$ is specified with respect to a set of atomic
concepts, $\mathrm{X}$ and a set of roles, $\mathrm{R}$:

$\alpha\ ::=\ \top\ |\ \bot\ |\ A\ |\
\left(\alpha\mathbf{?}\alpha\mathbf{:}\alpha\right)\ |\
[\rho]\left(\alpha\\!\mid\\!\alpha\right)$

where $A\in\mathrm{X}$ is an atomic concept, and $\rho\in\mathrm{R}$ is a
role. Let the set of $\mathrm{ADL}$ formulas generated by this syntax be
$\mathcal{L}_{\mathrm{ADL}}$. This syntax uses non-standard operators and the
following terminology is used: $\top$ is always; $\bot$ is never; $A$ is some
named concept that may hold for an individual;
$\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right)$ is if $\alpha$ then
$\beta$, else $\gamma$ (the conditional operator); and
$[\rho]\left(\alpha\\!\mid\\!\beta\right)$ is $\rho$ is $\alpha$ given $\beta$
(the marginalisation operator).

We also identify a special role $\mathtt{id}\in\mathrm{R}$ referred to as
identity, which essentially refers to different possibilities for the one
individual, and write $(\alpha\\!\mid\\!\beta)$ in place of
$[\mathtt{id}]\left(\alpha\\!\mid\\!\beta\right)$.

In these semantics every thing is interpreted as a probability dependent only
on the individual: $\top$ always has probability 1.0 and $\bot$ always has
probability 0.0; an atomic concept $A$ has some probability that is dependent
only on the current individual;
$\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right)$ has the probability of
$\beta$ given $\alpha$ or $\gamma$ given not $\alpha$; and
$[\rho]\left(\alpha\\!\mid\\!\beta\right)$ is the probability of $\alpha$
given $\beta$ over the set of individuals in the probability distribution
corresponding to $\rho$.

###  3.2 Motivation

Prior to giving formal semantics, this section gives an intuition for the new
operators. Imagine an agent, referred to as the aleator, who treats everything
as a gamble much like a game of dice. But as a shrewd gambler, the aleator
seeks to understand the dice, and know the probabilities better than anyone
else. In the aleator’s mental model of the world, every individual and every
entity can be modelled by a bag of dice:

To see if entity $e$ satisfies concept $C$, the aleator selects the bag of
dice labelled $e$, and then finds the die labelled $C$ in that bag. Every face
of that die is either assigned $\top$ or $\bot$. The aleator rolls the die,
and if $\top$ labels the upmost face, then $e$ satisfies $C$, this time.
Everything is a probability, and the next time the aleator plays this game,
the result may be different. But it’s the probability of winning (or coming up
$\top$) the aleator cares about, not some ideal truth. This is a simple game
(the game of $C$ at $e$), and the more complex expressions in the syntax can
build more complex games.

To see if entity $e$ satisfies the proposition
$\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right)$, the aleator first plays
the game of $\alpha$ at $e$. If it comes up $\top$, then the aleator plays the
game of $\beta$ at $e$. Otherwise, the aleator plays the game of $\gamma$ at
$e$, and in either case, the result of the second “game” is the final result.

To see if entity $e$ satisfies the proposition
$[\rho]\left(\alpha\\!\mid\\!\beta\right)$, the aleator finds the die labelled
$\rho$ in the bag of dice labelled $e$. This die is different to the dice
labelled by concepts: instead of faces assigned $\top$ and $\bot$, the faces
of this die are labelled with other entities. To evaluate the proposition the
aleator rolls the $\rho$ die, and notes the entity $e^{\prime}$ on the upmost
face. They then play the game of $\beta$ at $e^{\prime}$ (i.e. by taking the
bag of dice labelled $e^{\prime}$ and evaluating $\beta$). If this comes up
$\top$, the aleator then plays the game of $\alpha$ at $e^{\prime}$ and this
becomes the final result. If the game of $\beta$ at $e^{\prime}$ came up
$\bot$, then the aleator restarts the game, going back to the bag of $e$ dice
and rolling the $\rho$ die. This process continues for as long as necessary,
and if there is never a result, it defaults to $\top$.

This process maps every formula to either $\top$ or $\bot$ with a determined
probability. Thus it gives an aleatoric model of an agent’s beliefs. However,
we presume that the agent is uncertain as to the true bias of the dice. They
are simply Bayesian priors that an agent may refine through observation.

To put this in the context of the initial example, the aleator wants to know
the chance they have been exposed to a virus, given they were in contact with
someone who had a fever. The proposition the aleator wants to evaluate is as
follows:

$\left(\textit{virus}\mathbf{?}\top\mathbf{:}[\textit{contact}]\left(\textit{infectious}\\!\mid\\!\textit{fever}\right)\right)$

“If they were already (asymptomatically) infected, they remain infected.
Otherwise, given a contact selected from the population of people who have a
fever, what is the probability that the contact is infected with the virus”.

To evaluate this they roll a die, to see if they already have the virus (there
may be a 1% chance). In the cases where they didn’t already have the virus,
the aleator rolls a die to select a random person from the population of
contacts, and then checks the person has a fever by rolling a die that
represents the likelihood the person has a fever. This is repeated until a
random febrile contact is selected. Then a final die is rolled to determine
whether that person is infectious.

Aleatoric description logic does not describe the true world, nor does it
describe a typical rational agent. But it does describe a certain kind of
rational agent, who can tolerate uncertainty and incorporate new evidence into
their belief model in a simple and mathematically elegant way.

###  3.3 Probabilistic Semantics

The $\mathrm{ADL}$ is interpreted over an Aleatoric Belief Model, that is
based on the probability model of [7] and the probability structures defined
in [10]. It directly corresponds to the mental model of the aleator,
consisting of the bags of dice.

######  Definition 3.1.

Given a set $S$, we use the notation $\mathrm{PD}(S)$ to notate the set of
probability distributions over $S$, where $\mu\in\mathrm{PD}(S)$ implies:
$\mu:S\longrightarrow[0,1]$; and $\sum_{s\in S}\mu(s)=1$.

We use the notion of an aleatoric belief model as an interpretation of
$\mathrm{ADL}$.

######  Definition 3.2.

Given a set of atomic concepts $\mathrm{X}$, and a set of roles $\mathrm{R}$,
an aleatoric belief model is specified by the tuple $\mathcal{B}=(I,r,\ell)$,
where:

  * •

$I$ is a set of possible individuals.

  * •

$r:\mathrm{R}\times I\longrightarrow\mathrm{PD}(I)$ assigns for each role
$\rho\in\mathrm{R}$ and each individual $i\in I$, a probability distribution
$r(\rho,i)$ over $I$. We will typically write $\rho(i,j)$ in place of
$r(\rho,i)(j)$.

  * •

For the role $\mathtt{id}$, we include the additional constraint: for all
$i,j,k\in I$, $\mathtt{id}(i,j)>0$ implies
$\mathtt{id}(j,k)=\mathtt{id}(i,k)$.

  * •

$\ell:I\times\mathrm{X}\longrightarrow[0,1]$ gives the likelihood, $\ell(i,C)$
of an individual $i$ satisfying an atomic concept $C$. We will write $C(i)$ in
place of $\ell(C,i)$.

Given some $i\in I$, we let $\mathcal{B}_{i}$ be referred to as a pointed
aleatoric belief model.

######  Definition 3.3.

Given an aleatoric belief model $\mathcal{B}=(I,r,\ell)$, some $i\in I$, and
some $\alpha\in\mathrm{ADL}$ we specify the probability $\mathcal{B}$ assigns
$i$ satisfying $\alpha$, $\mathcal{B}_{i}(\alpha)$, recursively. We use the
abbreviation, where $\rho\in\mathrm{R}$: $E^{\rho}_{i}\alpha=\sum_{j\in
I}\rho(i,j)\mathcal{B}_{j}(\alpha)$. Then:

$\displaystyle\mathcal{B}_{i}(\bot)=0$
$\displaystyle\mathcal{B}_{i}(\top)=1\qquad\mathcal{B}_{i}(C)=C(i)$
$\displaystyle\mathcal{B}_{i}(\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right))$
$\displaystyle=$
$\displaystyle\mathcal{B}_{i}(\alpha).\mathcal{B}_{i}(\beta)+(1-\mathcal{B}_{i}(\alpha)).\mathcal{B}_{i}(\gamma)$
$\displaystyle\mathcal{B}_{i}([\rho]\left(\alpha\\!\mid\\!\beta\right))$
$\displaystyle=$ $\displaystyle\frac{\sum_{j\in
I}\rho(i,j)\mathcal{B}_{j}(\alpha)\mathcal{B}_{j}(\beta)}{E^{\rho}_{i}\beta}\
\textrm{if}\ E^{\rho}_{i}\beta>0$
$\displaystyle\mathcal{B}_{i}([\rho]\left(\alpha\\!\mid\\!\beta\right))$
$\displaystyle=$ $\displaystyle 1,\ \textrm{if}\ E^{\rho}_{i}\beta=0$

These semantics match the motivation of the aleator and the bag of dice. The
probability of the game of $C$ at $i$ coming up $\top$ is $C(i)$. When
evaluating $\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right)$ at $i$, note
the probabilities for the games of $\alpha$, $\beta$ and $\gamma$ at $i$ are
all independent. Therefore the values of the probabilities may be multiplied
together: the probability of $\alpha$ and $\beta$ coming up $\top$ at $i$ is
$\mathcal{B}_{i}(\alpha).\mathcal{B}_{i}(\beta)$, the probability of $\alpha$
coming up $\bot$ and $\gamma$ coming up $\top$ at $i$ is
$(1-\mathcal{B}_{i}(\alpha)).\mathcal{B}_{i}(\gamma)$, and since $\alpha$
coming up $\top$ and $\alpha$ coming up $\bot$ are mutually exclusive (the
game of $\alpha$ is only played once), these probabilities may be added
together. Finally, when evaluating $[\rho]\left(\alpha\\!\mid\\!\beta\right)$
we are simply taking the expectation of $\alpha$ over the distribution for
$\rho$, marginalised by the expectation of $\beta$ over the distribution for
$\rho$.

An important property of these semantics is the weak independence assumption:
All formulas of $\mathrm{ADL}$ are contingent only on the individual at which
they are evaluated. This means that two formulas evaluated at the same
individual may be viewed as independent probabilistic events.

Table 1 gives a set of abbreviations familiar in the context of description
logics.

Table 1: Some abbreviations of operators in $\mathrm{ADL}$. | term | formula | interpretation
---|---|---
$\alpha\sqcap\beta$ | $\left(\alpha\mathbf{?}\beta\mathbf{:}\bot\right)$ | $\mathcal{B}_{i}(\alpha).\mathcal{B}_{i}(\beta)$
$\alpha\sqcup\beta$ | $\left(\alpha\mathbf{?}\top\mathbf{:}\beta\right)$ | $\mathcal{B}_{i}(\alpha)+\mathcal{B}_{i}(\beta)-\mathcal{B}_{i}(\alpha).\mathcal{B}_{i}(\beta)$
$\lnot\alpha$ | $\left(\alpha\mathbf{?}\bot\mathbf{:}\top\right)$ | $1-\mathcal{B}_{i}(\alpha)$
$\alpha\Rightarrow\beta$ | $\left(\alpha\mathbf{?}\beta\mathbf{:}\top\right)$ | $1-\mathcal{B}_{i}(\alpha)+\mathcal{B}_{i}(\alpha).\mathcal{B}_{i}(\beta)$
$E_{\rho}\alpha$ | $[\rho]\left(\alpha\\!\mid\\!\top\right)$ | $\sum_{j\in I}\rho(i,j).\mathcal{B}_{j}(\alpha)$
$\exists\rho.\alpha$ | $\lnot[\rho]\left(\bot\\!\mid\\!\alpha\right)$ |  $1$ if $E_{\rho}\alpha\neq 0$, $0$ otherwise.
$\alpha^{\frac{n}{m}}=\left\\{\begin{array}[]{ll}1&\textrm{ if }n=0\\\
0&\textrm{ if }m<n\\\
\left(\alpha\mathbf{?}\alpha^{\frac{n-1}{m-1}}\mathbf{:}\alpha^{\frac{n}{m}}\right)&\textrm{
if }n<m\end{array}\right.$

The abbreviation in the right column of the table corresponds to a process of
repeated sampling: Where $n,m\in\omega$, $\alpha^{\frac{n}{m}}$ corresponds to
the likelihood of $\alpha$ being sampled at least $n$ times out of $m$. (A
similar abbreviation can be defined for $\alpha$ coming up $\top$ exactly $n$
times out of $m$.) Note that this does not describe a probability or
frequency, but an event. So $\alpha^{\frac{4}{5}}$ does not mean $\alpha$ is
sampled at least 80% of the time. Instead it describes the event of $\alpha$
being sampled $4$ times out of $5$, which would be quite likely (0.88) if
$\alpha$ had probability 0.8, and unlikely (0.19) if $\alpha$ had probability
0.5. This formalism can encode degrees of belief in an elegant way. If an
agent were to perform an action only if they believed $\alpha$ very strongly,
one might set $\alpha^{\frac{9}{10}}$ as a precondition for the action, and if
an agent were informed of a proposition $\beta$ by another agent who is
considered unreliable, they may update their belief base with the proposition
$\beta^{\frac{2}{3}}$.

These operators may not appear logical: $\sqcap$ is not idempotent, and
appears similar to the product t-norm of fuzzy logic [28]. However, Section 5
shows that these new operators are inherently probabilistic and represent the
process of reasoning over a probability space of description logic models.
Furthermore, restricting the concept probabilities to be 0 or 1, it can be
seen that the semantic interpretation of $\sqcap$, $\lnot$ and $\exists\rho$
agrees with the standard description logic semantics, so classical description
logic can be seen as a special case of aleatoric description logic.

###  3.4 Example

For example, suppose we have three agents: Hector, Igor and Julia. They each
may have a virus (V), or not, and they also may have a fever (F), whether they
have the virus or not. For each agent, we suppose that there are two possible
individuals (PI), one with the virus (e.g. Hector1) and one without (e.g.
Hector0). For each possible individual, there is probability of them having a
fever, which is naturally higher for possible individuals with the virus. Each
agent will occasionally come into contact with another agent, and the identity
of this agent is described by the probability distribution contact. Finally,
for each possible individual there is the probability of them being the actual
agent (id).

We can calculate the probability of an agent being newly exposed to the virus:

$E(\lnot V\sqcap[\mathtt{c}]\left(V\\!\mid\\!F\right))\preceq\mathtt{exp}$

An interpretation can be given this scenario. For each agent, we suppose that
there are two possible individuals (PI), one with the virus (e.g. Hector1) and
one without (e.g. Hector0). Note that the weighted probabilities of these
agents satisfy the constraints of the A-Book, $\mathcal{A}$.

The probabilities for this scenario are given in Table 2, and a graphical
representation is given in Figure 1.

Table 2: Initial probabilities for agent, contacts, virus and symptoms

PI | id | V | F | $\mathtt{H_{0}}$ | $\mathtt{H_{1}}$ | $\mathtt{I_{0}}$ | $\mathtt{I_{1}}$ | $\mathtt{J_{0}}$ | $\mathtt{J_{1}}$
---|---|---|---|---|---|---|---|---|---
Hector0 | 0.9 | 0.0 | 0.1 | 0.0 | 0.0 | 0.15 | 0.15 | 0.21 | 0.49
Hector1 | 0.1 | 1.0 | 0.6 | 0.0 | 0.0 | 0.15 | 0.15 | 0.21 | 0.49
Igor0 | 0.5 | 0.0 | 0.3 | 0.04 | 0.36 | 0.0 | 0.0 | 0.18 | 0.42
Igor1 | 0.5 | 1.0 | 0.8 | 0.04 | 0.36 | 0.0 | 0.0 | 0.18 | 0.42
Julia0 | 0.3 | 0.0 | 0.2 | 0.04 | 0.36 | 0.3 | 0.3 | 0.0 | 0.0
Julia1 | 0.7 | 1.0 | 0.9 | 0.04 | 0.36 | 0.3 | 0.3 | 0.0 | 0.0

Figure 1: A graphical example of the virus transmission scenario.

$\begin{array}[]{c}\mathtt{H_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.1\end{array}$ $\begin{array}[]{c}\mathtt{H_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.6\end{array}$
$\begin{array}[]{c}\mathtt{I_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.3\end{array}$ $\begin{array}[]{c}\mathtt{I_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.8\end{array}$
$\begin{array}[]{c}\mathtt{J_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.2\end{array}$ $\begin{array}[]{c}\mathtt{J_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.9\end{array}$
$\mathtt{id}$0.10.9$\mathtt{id}$0.50.5$\mathtt{id}$0.30.7$\mathtt{c}$0.40.3$\mathtt{c}$0.60.6$\mathtt{c}$0.70.4

Interpreting this for Hector, we see the probability Hector was newly exposed
to the virus is approximately 0.7. The working for this is shown in Table 3.

Table 3: A calculation of the chance of Hector being newly exposed with the virus, after a chance encounter with a person with a fever. $\mathtt{I_{0}}$ | $F_{\mathtt{I_{0}}}=0.3,\quad(V\sqcap F)_{\mathtt{I_{0}}}=0.0,\quad\mathtt{c}(\mathtt{H_{0}},\mathtt{I_{0}})=\mathtt{c}(\mathtt{H_{1}},\mathtt{I_{0}})=.15$
---|---
$\mathtt{I_{1}}$ | $F_{\mathtt{I_{1}}}=0.8,\quad(V\sqcap F)_{\mathtt{I_{0}}}=0.8,\quad\mathtt{c}(\mathtt{H_{0}},\mathtt{I_{0}})=\mathtt{c}(\mathtt{H_{1}},\mathtt{I_{0}})=.15$
$\mathtt{J_{0}}$ | $F_{\mathtt{J_{0}}}=0.2,\quad(V\sqcap F)_{\mathtt{J_{0}}}=0.0,\quad\mathtt{c}(\mathtt{H_{0}},\mathtt{J_{0}})=0.21,\quad\mathtt{c}(\mathtt{H_{1}},\mathtt{J_{0}})=.49$
$\mathtt{J_{1}}$ | $F_{\mathtt{J_{1}}}=0.9,\quad(V\sqcap F)_{\mathtt{J_{0}}}=0.9,\quad\mathtt{c}(\mathtt{H_{0}},\mathtt{J_{0}})=0.21,\quad\mathtt{c}(\mathtt{H_{1}},\mathtt{J_{0}})=.49$
$\mathtt{H_{0}}$ | $V_{0}=0.0,\quad\mathtt{id}_{0}=0.9,\quad[\mathtt{c}]\left(V\\!\mid\\!F\right)=\frac{\sum_{x=\mathtt{I_{0}}}^{\mathtt{J_{1}}}\mathtt{c}(\mathtt{H_{0}},x)\cdot(V\sqcap F)_{x}}{\sum_{x=\mathtt{I_{0}}}^{\mathtt{J_{1}}}\mathtt{c}(\mathtt{H_{0}},x).F_{x}}=0.78$
$\mathtt{H_{1}}$ | $V_{1}=1.0,\quad\mathtt{id}_{1}=0.1,\quad[\mathtt{c}]\left(V\\!\mid\\!F\right)=\frac{\sum_{x=\mathtt{I_{0}}}^{\mathtt{J_{1}}}\mathtt{c}(\mathtt{H_{1}},x)\cdot(V\sqcap F)_{x}}{\sum_{x=\mathtt{I_{0}}}^{\mathtt{J_{1}}}\mathtt{c}(\mathtt{H_{1}},x)\cdot F_{x}}=0.78$
$\mathtt{H}$ | $E(\lnot V\sqcap[\mathtt{c}]\left(V\\!\mid\\!F\right))=\sum_{x=0}^{1}(1-V_{x})\cdot\mathtt{id_{x}}.[\mathtt{c}]\left(V\\!\mid\\!F\right)=0.7$

##  4 Aleatoric Knowledge Base Semantics

A description logic knowledge base is defined as $\mathcal{K=\langle
T,A\rangle}$; where $\mathcal{K}$ is a knowledge base; $\mathcal{T}$, a TBox
is a set of axioms on the properties of concepts, known as intensional
assertions; and $\mathcal{A}$, an ABox, is a set of axioms on the groundings
of concepts, called extensional assertions [2].

The aleatoric belief models of Section 3.3 describe a complete interpretation
for formulas of aleatoric description logic, and so requires a notion of a
closed world. For the representations of an agent’s subjective knowledge in an
open world, it is only possible to record a subset of what the agent knows and
believes, and consider the class of all models that support this belief set.
Just as description logics are applied to knowledge bases consisting of
assertional axioms (A-Boxes) and terminological axioms, aleatoric description
logics are applied to aleatoric knowledge bases consisting of assertional
axioms (A-Books) and terminological axioms (T-Books).

An aleatoric knowledge base is defined over the same signature of atomic
concepts $\mathrm{X}$, and roles $\mathrm{R}$, including ${\mathtt{id}}$.
Additionally there is a set of named individuals, $\mathrm{N}$, which may be
thought of as special concepts for grounding assertions and framing queries.
In line with the epistemic nature of these knowledge bases each named
individual can be any one of a number of possible individuals, and the
distribution of these possible individuals is represented by the role
$\mathtt{id}$.

As with $\mathcal{ALC}$ we have terminological axioms and assertional axioms.
Aleatoric terminological axioms or T-Books describe rules that are universally
true for all individuals, and thus provide a non-probabilistic intensional
definition of the concepts and roles in the logic. Aleatoric assertional
axioms or A-Books describe subjective extensional information by listing the
probabilities with which individuals satisfy given concepts and roles. It is
not the case that T-Books describe concept inclusion nor subsumption as TBoxes
do in $\mathcal{ALC}$, as these concepts do not make sense when considering a
set of weakly independent propositions. Instead T-Books, provide a means to
constrain strength of belief. The semantics are given in Definition 4.1.

######  Definition 4.1.

The aleatoric terminological axioms have the form:

$\begin{array}[]{cl}\alpha\preceq\beta&\alpha\textrm{ is no more likely than
}\beta\\\ \alpha\approx\beta&\alpha\textrm{ is exactly as likely as
}\beta.\end{array}$

Given an aleatoric belief model $\mathcal{B}=(I,R,\ell)$, $\mathcal{B}$
satisfies $\alpha\preceq\beta$ (written
$\mathcal{B}\models\alpha\preceq\beta$), if and only if for all $i\in I$,
$\mathcal{B}_{i}(\alpha)\leq\mathcal{B}_{i}(\beta)$; and $\mathcal{B}$
satisfies $\alpha\approx\beta$ (written
$\mathcal{B}\models\alpha\approx\beta$) if and only if
$\mathcal{B}\models\alpha\preceq\beta$ and
$\mathcal{B}\models\beta\preceq\alpha$. A T-Book is a set of aleatoric
terminological axioms.

These axioms place universal constraints on the likelihoods of aleatoric
formulas being true. For example we might include an axiom
$\textit{first}\preceq\textit{place}$, meaning coming first in a race is no
more likely than placing (coming first, second or third). Alternatively, we
could define placing precisely as coming first, second or third, via the axiom
$\textit{place}\approx\textit{first}\sqcup\textit{second}\sqcup\textit{third}$,
and then $\textit{first}\preceq\textit{place}$ is implicitly true.

######  Definition 4.2.

The aleatoric assertional axiom (or simply assertions) have the form:

  * •

$a:^{p}\alpha$, where $a\in\mathrm{N}$, $p\in[0,1]$ and
$\alpha\in\mathrm{ADL}$ asserts that individual $a$ satisfies concept
$\alpha$, with probability $p$.

  * •

$(a,b):^{p}\rho$, where $a,b\in\mathrm{N}$, $p\in[0,1]$ and
$\rho\in\mathrm{R}$ asserts that individual $b$ satisfies the role $\rho$ for
$a$ with probability $p$.

An a-book $\mathcal{A}$ is a set of aleatoric assertional axioms, and
$\mathcal{A}$ is a well-formed a-book if for every $a\in N$, for every
$\rho\in R$, $\sum\\{p\ |\ (a,b):^{p}\rho\\}\leq 1$. An A-Book, $\mathcal{A}$
is simple if for all aleatoric assertional axioms $\sigma\in\mathcal{A}$ of
the form $a:^{p}\alpha$, it is the case that $\alpha$ is an atomic concept.

While an A-Book is existentially quantified, T-Books are universally
quantified and consequently a very powerful formalism. Therefore, it is useful
to consider a restriction on T-Books referred to as an acyclic T-Book.

######  Definition 4.3.

A concept $C$ is an atom if $C\in\mathrm{X}\cup\\{\top,\bot\\}$ (i.e. $C$ is
an atomic concept, always, or never). A terminological axiom is simple if it
has the one of the forms

  * •

$C\approx\left(D\mathbf{?}E\mathbf{:}F\right)$ where $C,\ D,\ E$ and $F$ are
all atoms.

  * •

$C\approx[\rho]\left(D\\!\mid\\!E\right)$ where $C,\ D$ and $E$ are all atoms.

A simple T-Book, $\mathcal{T}$, is a T-Book consisting only of simple
terminological axioms. A simple T-Book, $\mathcal{T}$, is acyclic if there is
no sequence of concepts $C_{0},\ldots,C_{n}$ where:

  * •

for all $i=1,\ldots,n$, either:

    * –

there is some $C\approx\left(D\mathbf{?}E\mathbf{:}F\right)\in\mathcal{T}$,
where $C_{i},C_{i-1}\in\\{C,D,E,F\\}\cap\mathrm{X}$;

    * –

there is some $C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, where
$C_{i},C_{i-1}\in\\{C,D,E\\}\cap\mathrm{X}$;

  * •

there is some $i$ where
$C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$ and
$C_{i},C_{i-1}\in\\{C,D,E\\}\cap\mathrm{X}$;

  * •

$C_{0}=C_{n}$.

As a brief example of a useful terminological axiom the following axiom
constrains the concept $C_{\textit{fair}}$ to be a fair coin:
$C_{\textit{fair}}\approx\lnot C_{\textit{fair}}$. Now for all individuals,
one can assume that there is a concept, $C_{\textit{fair}}$, available that
has precisely a half chance of coming up $\top$.

A simple T-Book and a simple A-Book make a simple aleatoric knowledge base.

######  Definition 4.4.

An aleatoric knowledge base $\mathcal{K}=(\mathcal{A},\mathcal{T})$ is a pair
consisting of a set of assertional axioms $\mathcal{A}$ and a set of
terminological axioms $\mathcal{T}$. If $\mathcal{A}$ is a simple A-Book and
$\mathcal{T}$ is a simple T-Book, the $\mathcal{K}$ is a simple aleatoric
knowledge base, and if $\mathcal{T}$ is also acyclic $\mathcal{K}$ is an
acyclic simple knowledge base.

An aleatoric knowledge base describes a belief, or subjective position of an
agent, that can correspond to a number of different interpretations. The
interpretations satisfy the aleatoric knowledge base if they make all the
axioms true.

######  Definition 4.5.

Given an aleatoric knowledge base $\mathcal{K}=(\mathcal{A},\mathcal{T})$ over
the signature ($\mathrm{X}$, $\mathrm{R}$, $\mathrm{N}$), and an aleatoric
belief model $\mathcal{B}=(I,r,\ell)$ over the signature
($\mathrm{X}\cup\mathrm{N}$, $\mathrm{R}$) satisfies $\mathcal{K}$ iff:

  * •

For every $a\in\mathrm{N}$, for every $i\in I$, $a(i)\in\\{0,1\\}$ and for all
$i,j\in I$, $a(i)=1$ and $\mathtt{id}(i,j)>0$ implies $a(j)=1$. That is, the
names are absolute concepts, and two possibilities for a single individual
will share a name.

  * •

For every terminological axiom $\alpha\preceq\beta\in\mathcal{T}$, for every
$i\in I$, it follows that $\mathcal{B}_{i}(\alpha)\leq\mathcal{B}_{i}(\beta)$.

  * •

For every terminological axiom $\alpha\approx\beta\in\mathcal{T}$, for every
$i\in I$, it follows that $\mathcal{B}_{i}(\alpha)=\mathcal{B}_{i}(\beta)$.

  * •

For every assertion $a:^{p}\alpha\in\mathcal{A}$, for every $i\in I$ with
$a(i)=1$, it follows that $\mathcal{B}_{i}(E\alpha)=p$.

  * •

For every assertion $(a,b):^{p}\rho\in\mathcal{A}$ for every $i\in I$ with
$a(i)=1$, $\sum_{j\in I}\rho(i,j).b(j)=p$.

We say that a knowledge base $\mathcal{K}$ is consistent if it is supported by
at least one aleatoric belief model.

The following lemma is a useful simplification.

######  Lemma 4.6.

Every aleatoric knowledge base $\mathcal{K}=(\mathcal{A},\mathcal{T})$ is
equivalent to a simple aleatoric knowledge base, $\mathcal{K}^{\prime}$.

#### Proof:

For every terminological axiom $\tau\in\mathcal{T}$ introduce a fresh atomic
concept $E_{\tau}$; for every non-atomic subformula $\alpha$ appearing in some
terminological or assertional axioms $\tau\in\mathcal{A}\cup\mathcal{T}$,
introduce a fresh atomic concept $C_{\alpha}$; and for every atomic concept
$\alpha\in\mathrm{X}$ appearing in some axiom
$\tau\in\mathcal{A}\cup\mathcal{T}$, let $C_{\alpha}=\alpha$. If
$\alpha=\left(\beta\mathbf{?}\gamma\mathbf{:}\delta\right)$, then let
$\alpha^{*}=\left(C_{\beta}\mathbf{?}C_{\gamma}\mathbf{:}C_{\delta}\right)$,
and if $\alpha=[\rho]\left(\beta\\!\mid\\!\gamma\right)$,
$\alpha^{*}=[\rho]\left(C_{\beta}\\!\mid\\!C_{\gamma}\right)$. The T-Book,
$\mathcal{T}^{\prime}$ is then the set of axioms:

$\left\\{\begin{array}[]{ll}C_{\alpha}\approx\alpha^{*}&|\ \alpha\textrm{
appears in }\tau\in\mathcal{A}\cup\mathcal{T}\\\ C_{\alpha}\approx
C_{\beta}&|\ \alpha\approx\beta\in\mathcal{T}\\\
C_{\alpha}\approx\left(C_{\beta}\mathbf{?}E_{\tau}\mathbf{:}\bot\right)&|\
\tau=\alpha\preceq\beta\in\mathcal{T}\end{array}\right\\},$

the A-Book, $\mathcal{A}$’, is

$\left\\{\begin{array}[]{ll}a:^{p}C_{\alpha}&|\ a:^{p}\alpha\in\mathcal{A}\\\
(a,b):^{p}\rho&|\ (a,b):^{p}\rho\in\mathcal{A}\end{array}\right\\},$

and $\mathcal{K}^{\prime}=(\mathcal{A}^{\prime},\mathcal{T}^{\prime})$. It is
easy to see that given any aleatoric belief model $\mathcal{B}=(I,R,\ell)$
satisfying $\mathcal{K}$, a corresponding aleatoric belief model
$\mathcal{B}^{\prime}=(I,R,\ell)$ may be defined to satisfy
$\mathcal{K}^{\prime}$ by setting, for all $i\in I$, for all $\alpha$
appearing in $\tau\in\mathcal{A}\cup\mathcal{T}$,
$\ell^{\prime}(i,C_{\alpha})=\mathcal{B}_{i}(\alpha)$, and for all $i\in I$,
for all $\tau=\alpha\preceq\beta\in\mathcal{T}$ setting
$\ell^{\prime}(i,E_{\tau})=\mathcal{B}_{i}(\alpha)/\mathcal{B}_{i}(\beta)$
(this is guaranteed to be between 0 and 1, since $\mathcal{B}$ satisfies
$\alpha\preceq\beta$). $\square$

For an aleatoric knowledge the questions of interest are:

  * •

Satisfiability: Given an aleatoric knowledge base,
$\mathcal{K}=(\mathcal{A},\mathcal{T})$, is it consistent.

  * •

Concept Satisfiability: Given an aleatoric knowledge base,
$\mathcal{K}=(\mathcal{A},\emptyset)$, is it consistent.

  * •

Concept query: Given an aleatoric knowledge base,
$\mathcal{K}=(\mathcal{A},\mathcal{T})$, what is the lower (upper) bound on
the likelihood of a concept for some named individual.

The following subsection extend the example of Section 3.4 to the aleatoric
knowledge base semantics, and then the subsequent section will consider the
complexity of answering these questions.

###  4.1 Example

The case from Section 3.4 can now be expressed as an aleatoric knowledge base.
Now, rather than needing to assign a probability to every role and concept,
only the propositions an agent has a genuine subjective position on are given.

For example, an aleatoric knowledge base could model that Hector is very
likely not to have the virus; Julia is likely to have the virus, Julia is very
likely to have a fever and to it is likely that Hector came into contact with
Julia. Furthermore, a terminological axiom can specify the belief that a new
exposure to the virus ($\mathtt{exp}$) occurs if an agent did not already have
the virus, but came into contact with some febrile person who did have the
virus. Thus the aleatoric knowledge base
$\mathcal{K}=(\\{\mathcal{T}_{1}\\},\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{4}\\}$
is:

$\begin{array}[]{ll}\mathcal{A}_{1}&\mathtt{Hector}:^{0.1}V\\\
\mathcal{A}_{2}&\mathtt{Julia}:^{0.7}V\\\
\mathcal{A}_{3}&\mathtt{Julia}:^{0.69}F\\\
\mathcal{A}_{4}&(\mathtt{Hector},\mathtt{Julia}):^{0.3}\mathtt{c}\\\
\mathcal{T}_{1}&E(\lnot
V\sqcap[\mathtt{c}]\left(V\\!\mid\\!F\right))\preceq\mathtt{exp}\end{array}$

This aleatoric knowledge base is satisfied by the interpretation presented in
Section 3.4. However, many other interpretations would also satisfy
$\mathcal{K}$. Igor, the other possible contact of Hector, does not appear in
the knowledge base, so in the 70% chance that Julia was not a contact of
Hector, the actual contact is truly arbitrary. Therefore, the knowledge base
semantics do not require one to take a position on propositions they have no
information on (subjective or otherwise). The aleatoric knowledge base can be
used to answer queries. To determine if the knowledge base necessitates that
there is a greater than 25% chance of Hector being newly exposed to the virus,
the axiom $\mathtt{Hector}:^{0.25}\mathtt{exp}$ can be inserted into the
knowledge base, and consistency checking can be applied. This process is
described in the following section.

###  4.2 Reasoning with Aleatoric Description Logic

This section will consider computational properties of aleatoric description
logic. The particular questions considered are:

  * •

Model Checking Given an pointed belief model $B_{i}$ and some formula
$\alpha$, what is the value of $B_{i}(\alpha)$ (the probability assigned to
$\alpha$ by $B_{i}$).

  * •

Belief Set Consistency Given a belief set
$\mathcal{K}=(\mathcal{T},\mathcal{A})$, is there a belief model that agrees
with the belief set on all axioms.

An aleatoric knowledge base may correspond to many aleatoric belief models, or
possibly none. The main question of interest is whether there is any
interpretation that could possibly correspond to a given aleatoric knowledge
base. However, by assigning flat priors to all unknown (or ambivalent
concepts) one can define an interpretation and get a partial answer via model-
checking.

######  Lemma 4.7.

Given a pointed belief model $\mathcal{B}_{i}$ consisting of $n$ possible
individuals, and a formula $\alpha$ consisting of $m$ symbols, the value
$\mathcal{B}_{i}(\alpha)$ can be computed in time $O(n^{2}m)$.

#### Proof:

This computation is done by applying the semantic definitions recursively. All
operations can be done in constant time ($O(1)$) except marginalisation which
is $O(n)$. As operations need to be done for every possible individual, and
there are at most $m$ operations, the complexity has an upper bound of
$O(n^{2}m)$. $\square$

To be able to perform inference based on an aleatoric knowledge base, we must
first determine if it is consistent (i.e. agrees with at least one aleatoric
belief model). Given a simple aleatoric knowledge base
$\mathcal{K}=(\mathcal{T},\mathcal{A})$, where $\mathcal{T}$ is an acyclic
t-book, it is possible to determine if $\mathcal{K}$ is satisfiable with
complexity PSPACE. The case for non-acyclic t-books is left to future work.

The process for the satisfiability theorem is to build a system of polynomial
equalities and inequalities corresponding to the axioms in $\mathcal{K}$. This
system of constraints is satisfiable if and only if $\mathcal{K}$ is
satisfiable. The system of equalities corresponds closely to the semantic
interpretation of the axioms, over a sufficiently large set of individuals,
that are constrained by linear inequalities. Given an aleatoric knowledge base
$\mathcal{K}=(\mathcal{T},\mathcal{A})$, let $\Lambda^{\mathcal{K}}$ be a set
of variables, let $\Phi^{\mathcal{K}}$ be a set of polynomial equalities over
$\Lambda^{\mathcal{K}}$, and let $\Psi^{\mathcal{K}}$ be a set of linear
inequalities over $\Lambda^{\mathcal{K}}$. These sets are constructed as
follows.

As $\mathcal{T}$ is simple and acyclic, it will only contain axioms of the
form: $C\approx\left(D\mathbf{?}E\mathbf{:}F\right)$,
$C\approx[\rho]\left(D\\!\mid\\!E\right)$ and $C\approx D$, where $C$, $D$,
and $E$ are all atomic. Define the relation $\cong\subseteq\mathrm{X}^{2}$
over the set of atomic concepts by:

  1. 1.

for all $Cin\mathrm{X}$, $C\cong C$,

  2. 2.

$C\cong D$ and $D\cong E$, implies $C\cong E$,

  3. 3.

if $C\approx\left(D\mathbf{?}E\mathbf{:}F\right)\in\mathcal{T}$, then $X\cong
Y$ for all $X,Y\in\\{C,D,E,F\\}\cap\mathrm{X}$.

  4. 4.

if $C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, and
$C,D\in\mathrm{X}$, then $D\cong E$, and $E\cong D$

  5. 5.

if $C\approx D\in\mathcal{T}$ and $C,D\in\mathrm{X}$, then $C\cong D$, and
$D\cong C$.

It is clear that $\cong$ is an equivalence relation, so for every atomic
concept $C\in\mathrm{X}$ let $\overline{C}$ be the corresponding equivalence
class. Let $\overline{\mathrm{X}}$ be the set of equivalence classes,
$\overline{C}$, where $C\in\mathrm{X}$, Given
$\overline{C},\overline{D}\in\overline{\mathrm{X}}$, and $\rho\in\mathrm{R}$,
let $\rho^{\\#}(\overline{C},\overline{C})$ be the number of axioms
$E\approx[\rho]\left(F\\!\mid\\!G\right)$ that appear in $\mathcal{T}$, where
$E\in\overline{C}$ and $\\{F,G\\}\cap c\neq\emptyset$. Let $c\Rightarrow d$ if
and only if for some $\rho\in\mathrm{R}$,
$\rho^{\\#}(\overline{C},\overline{D})>0$, or if $\overline{C}\in\mathrm{N}$
and $\overline{D}\notin\mathrm{N}$. Then $(\overline{\mathrm{X}},\Rightarrow)$
is a directed acyclic graph.

For each node of the graph, $\overline{C}\in\overline{\mathrm{X}}$, define:

$\\#\overline{C}=\sum_{\begin{array}[]{c}\rho\in\mathrm{R}\\\
\overline{D}\in\overline{\mathrm{X}}\end{array}}\rho^{\\#}(\overline{D},\overline{C})$

so $\\#\overline{C}$ is the number of TBook axioms that contain a concept
related to $c$ in the scope of a marginalisation operator.

For each $\overline{C}\in\overline{\mathrm{X}}$, for each atomic concept
$D\in\overline{C}$, assign $\\#\overline{C}$ different variables
$x_{1}^{D},\ldots,x^{D}_{\\#\overline{C}}\in\Lambda^{\mathcal{K}}$, and add
the inequalities $\\{0\leq x_{i}^{D}\leq 1\ |\ D\in\overline{C},\
i=1,\ldots,\\#\overline{C}\\}$ to $\Psi^{\mathcal{K}}$. The following
equations are added to $\Phi^{\mathcal{K}}$, supposing that for all $i$,
$x^{\top}_{i}=1$ and $x^{\bot}_{i}=0$:

  * •

For each axiom of the form $C\approx(D?E:F)\in\mathcal{T}$ add to
$\Phi^{\mathcal{K}}$ the equations

$x^{C}_{i}=x^{D}_{i}.x^{E}_{i}+(1-x^{D}_{i}).x^{F}_{i},\ \textrm{ for
}i=1,\ldots\\#\overline{C},$

noting that it must be the case $D,E,F\in c\cup\\{\top,\bot\\}$.

  * •

For each axiom of the form $C\approx D\in\mathcal{T}$, add to
$\Phi^{\mathcal{K}}$ the equations $x^{C}_{i}=x^{D}_{i}$ for
$i=1,\ldots,\\#\overline{C}$.

For every $\rho\in\mathrm{R}$, for every pair
$\overline{C},\overline{D}\in\overline{\mathrm{X}}$, add the variables
$\\{r^{\overline{C}\rho\overline{D}}_{ij}\ |\ i=1,\ldots\\#\overline{C},\
j=1,\ldots,\\#\overline{D}\\}$ to $\Lambda^{\mathcal{K}}$, and add the
inequalities $\\{0\leq r^{\overline{C}\rho\overline{D}}_{ij}\leq 1\ |\
i=1,\ldots\\#\overline{C},\ j=1,\ldots,\\#\overline{D}\\}$ to
$\Psi^{\mathcal{K}}$. The following equations are added to
$\Phi^{\mathcal{K}}$:

  * •

For every pair $\overline{C},\overline{D}\in\overline{\mathrm{X}}$, for every
$\rho\in\mathrm{R}$, for each $i=1,\ldots,\\#\overline{C}$, add to
$\Phi^{\mathcal{K}}$ the equations
$\sum_{j=1}^{\\#\overline{D}}r^{\overline{C}\rho\overline{D}}_{ij}=1$.

  * •

For every axiom $C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, for
$i=1,\ldots,\\#\overline{C}$, add to $\Phi^{\mathcal{K}}$ the equation:

$\sum_{j=1}^{\\#\overline{D}}r^{\overline{C}\rho\overline{D}}_{ij}.x_{j}^{E}.x_{i}^{C}=\sum_{j=1}^{\\#d}r^{\overline{C}\rho\overline{D}}.x^{D}_{j}.x^{E}_{j},$

noting that $E\in\overline{D}\cup\\{\top,\bot\\}$.

  * •

To account for the case where
$C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, and $E$ is false, add
the variables $\\{e^{\overline{C}\rho\overline{D}}_{i}\
|\i=1,\ldots,\\#\overline{C}\\}$ to $\Lambda^{\mathcal{K}}$, along with the
inequalities: $\\{0\leq e^{\overline{C}\rho\overline{D}}_{i}\
|\i=1,\ldots,\\#\overline{C}\\}$ to $\Phi^{\mathcal{K}}$. Note, these are not
constrained to be less than 1. Then, add to $\Phi^{\mathcal{K}}$ the
equalities:

$(\sum_{j=1}^{\\#\overline{D}}r^{\overline{C}\rho\overline{D}}_{ij}.x_{j}^{E}).e^{\overline{C}\rho\overline{D}}_{i}+x_{i}^{C}=1.$

Therefore if
$\sum_{j=1}^{\\#\overline{C}}r^{\overline{C}\rho\overline{D}}_{ij}.x_{j}^{E}=0$
then $x_{i}^{C}$ must equal 1.

  * •

The $\mathtt{id}$ relation has additional constraints which are captured by
adding to $\Phi^{\mathcal{K}}$, for all
$\overline{C}\in\overline{\mathrm{X}}$, for every
$i,j,k=1,\ldots,\\#\overline{C}$, the equality
$r^{\overline{C}\mathtt{id}\overline{C}}_{ij}=r^{\overline{C}\mathtt{id}\overline{C}}_{ik}$.

Where $D,E\in\overline{C}$, for each $i=1,\ldots\\#\overline{C}$, the
variables $x^{D}_{i}$ and $x^{E}_{i}$ describe the probability of the concepts
$D$ and $E$ holding at the same individual. To build a complete model it is
necessary to describe a correspondence between different partitions of
concepts, as they will be describing different concepts for a common
individual.

For every $\overline{C},\overline{D}\in\overline{\mathrm{X}}$, add the
variables $\\{e^{\overline{C}\overline{D}}_{ij}\ |\
i=1,\ldots,\\#\overline{C},\ j=1,\ldots,\\#\overline{D}\\}$ to
$\Lambda^{\mathcal{K}}$, and add the inequalities $\\{0\leq
e^{\overline{C}\overline{D}}_{ij}\leq 1\ |\ i=1,\ldots,\\#\overline{C},\
j=1,\ldots,\\#\overline{D}\\}$ to $\Psi^{\mathcal{K}}$. The following
equalities are added to $\Phi^{\mathcal{K}}$:

  * •

For all $\overline{C}\in\overline{\mathrm{X}}$, for all
$i=1,\ldots,\\#\overline{C}$, add $e^{\overline{C}\overline{C}}_{ii}=1$.

  * •

For all $\overline{C},\overline{D}\in\overline{\mathrm{X}}$, for all
$i=1,\ldots,\\#\overline{C}$,
$\sum_{j=1}^{\\#d}e^{\overline{C}\overline{D}}_{ij}=1$.

  * •

For all $\overline{C},\overline{D},\overline{E}\in\overline{\mathrm{X}}$, for
all $i=1,\ldots,\\#\overline{C}$, for all $j=1,\ldots,\\#\overline{D}$, for
all $\rho\in\mathrm{R}$,

$e^{\overline{C}\overline{D}}_{ij}.\sum_{k=1}^{\\#\overline{E}}r^{\overline{D}\rho\overline{E}}_{jk}=e^{\overline{D}\overline{C}}_{ji}.\sum_{k=1}^{\\#\overline{E}}r^{\overline{C}\rho\overline{E}}_{ik}.$

  * •

For all $\overline{C},\overline{D},\overline{E}\in\overline{\mathrm{X}}$, for
all $i=1,\ldots,\\#\overline{C}$,

$\sum_{k=1}^{\\#\overline{E}}\sum_{j=1}^{\\#\overline{D}}r^{\overline{C}\rho\overline{D}}_{ij}.e^{\overline{D}\overline{E}}_{jk}=\sum_{j=1}^{\\#\overline{D}}\sum_{k=1}^{\\#\overline{E}}r^{\overline{C}\rho\overline{E}}_{ik}.e^{\overline{E}\overline{D}}_{kj}.$

It is left to represent the axioms in $\mathcal{A}$. For every
$a\in\mathrm{N}$, let $\\#a$ be the number of axioms in $\mathcal{A}$ that $a$
appears in, and for every $C\in\mathrm{X}$, for every $i=1,\ldots,\\#a$, add a
fresh variable $n^{aC}_{i}$ to $\Lambda^{\mathcal{K}}$. For every
$a\in\mathrm{N}$, for every $C\in\mathrm{X}$, for $i=1,\ldots,\\#a$ add the
inequalities $0\leq n^{ac}_{i}\leq 1$ to $\Psi^{\mathcal{K}}$.

For every $a\in\mathrm{N}$, for every $\rho\in\mathrm{R}$, for every
$\overline{C}\in\overline{\mathrm{X}}$, for $i=1,\ldots,\\#a$, for
$j=1,\ldots,\\#\overline{C}$, add a variable $r^{a\rho C}_{ij}$ to
$\Lambda^{\mathcal{K}}$, and add the inequalities $0\leq r^{a\rho C}_{ij}\leq
1$ to $\Psi^{\mathcal{K}}$. For every $a,b\in\mathrm{N}$ for
$i=1,\ldots,\\#a$, for $j=1,\ldots,\\#b$, add a variable
$r^{a\mathtt{id}b}_{ij}$ to $\Lambda^{\mathcal{K}}$, add the inequalities
$0\leq r^{a\mathtt{id}a}_{ij}\leq 1$ to $\Psi^{\mathcal{K}}$, and for every
$i,j,k=1,\ldots,\\#a$, add the equality
$r^{a\mathtt{id}a}_{ij}=r^{a\mathtt{id}a}_{ik}$ to $\Phi^{\mathcal{K}}$.

  * •

For each axiom $a:^{x}C$ in the simple A-Book $\mathcal{A}$, for every
$i=1,\ldots,\\#a$, add the equality
$\sum_{i=1}^{\\#a}r^{a\mathtt{id}a}_{ij}n^{ac}_{j}=x$ to $\Phi^{\mathcal{K}}$.

  * •

For each axiom $(a,b):^{x}\rho$, for every $i=1,\ldots,\\#a$ add the equality

$\sum_{j=1}^{\\#a}r^{a\mathtt{id}a}_{ij}\sum_{k=1}^{\\#b}r^{a\rho b}_{jk}=x$

to $\Phi^{\mathcal{K}}$.

  * •

For every $\overline{C}\in\overline{\mathrm{X}}$, for every
$\rho\in\mathrm{R}$, for each $i=1,\ldots,\\#a$, add to $\Phi^{\mathcal{K}}$
the equations

$\sum_{j=1}^{\\#\overline{C}}r^{a\rho\overline{C}}_{ij}+\sum_{b\in\mathrm{N}}\sum_{j=1}^{\\#b}r^{a\rho
b}_{ij}=1.$

  * •

For every axiom $C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, for
$i=1,\ldots,\\#a$, add to $\Phi^{\mathcal{K}}$ the equations:

$(\sum_{j=1}^{\\#\overline{D}}r^{a\rho\overline{D}}_{ij}.x_{j}^{E}+\sum_{b\in\mathrm{N}}\sum_{j=1}^{\\#b}r^{a\rho
b}n^{bE}_{j}).n_{i}^{aC}=\sum_{j=1}^{\\#\overline{D}}r^{a\rho\overline{D}}.x^{D}_{j}.x^{E}_{j}+\sum_{b\in\mathrm{N}}\sum_{j=1}^{\\#b}r^{a\rho
b}n^{bD}_{j}.n^{bE}_{j}.$

  * •

To account for the case where
$C\approx[\rho]\left(D\\!\mid\\!E\right)\in\mathcal{T}$, and $E$ is false, add
the variables $\\{e^{a\rho\overline{D}}_{i}\ |\i=1,\ldots,\\#\overline{C}\\}$
to $\Lambda^{\mathcal{K}}$, along with the inequalities: $\\{0\leq
e^{a\rho\overline{D}}_{i}\ |\i=1,\ldots,\\#a\\}$ to $\Phi^{\mathcal{K}}$.
Then, add to $\Phi^{\mathcal{K}}$ the equalities:

$(\sum_{j=1}^{\\#\overline{D}}r^{a\rho\overline{D}}_{ij}.x_{j}^{E}).e^{a\rho\overline{D}}_{i}+n^{aC}_{i}=1.$

  * •

For all $a\in\mathrm{N}$, for all
$\overline{D},\overline{E}\in\overline{\mathrm{X}}$, for all
$i=1,\ldots,\\#a$, for all $\rho\in\mathrm{R}$,

$\sum_{k=1}^{\\#\overline{E}}\sum_{j=1}^{\\#\overline{D}}r^{a\rho\overline{D}}_{ij}.e^{\overline{D}\overline{E}}_{jk}=\sum_{j=1}^{\\#\overline{D}}\sum_{k=1}^{\\#\overline{E}}r^{a\rho\overline{E}}_{ik}.e^{\overline{E}\overline{D}}_{kj}.$

This gives a set of equalities, $\Phi^{\mathcal{K}}$, and inequalities
$\Psi^{\mathcal{K}}$ over the variables $\Lambda^{\mathcal{K}}$, such that any
solution to these equations can be converted into an aleatoric belief model
$\mathcal{B}=(I,r,\ell)$ that satisfies $\mathcal{K}$. This construction is as
follows:

  * •

Enumerate $\overline{\mathrm{X}}$ as $X_{1},\ldots,X_{n}$. The set of
individuals, $I$, is the union of $\\{a_{1},\ldots,a_{\\#a}\ |\
a\in\mathrm{N}\\}$ and the set

$\\{(x_{1},\ldots,x_{n})\in\omega^{n}|\ \forall i\leq n,x_{i}\leq\\#X_{i},\
\forall i,j\leq n,e^{X_{i}X_{j}}_{x_{i}x_{j}}>0\\}$

  * •

Given $\rho\in\mathrm{R}$, and
$a_{i},b_{j},(x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n})\in I$:

    * –

$\rho(a_{i},b_{j})=r^{a\rho b}_{ij}$

    * –

$\rho(a_{i},(x_{1},\ldots,x_{n}))=r^{a\rho
X_{1}}_{ix_{1}}.e^{X_{1}X_{n}}_{x_{1}x_{n}}$

    * –

$\rho((x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n}))=e^{X_{1}X_{n}}_{x_{1}x_{n}}r^{X_{n}Y_{n}}_{x_{n}y_{n}}e^{Y_{n}Y_{1}}_{y_{n}y_{1}}$

    * –

$\rho((x_{1},\ldots,x_{n}),a_{i})=0$.

Note here, that from the constraints on $e^{X_{i}X_{j}}_{x_{i}x_{j}}$ the
choice of indices in the above equalities is inconsequential.

  * •

Given $C\in\mathrm{X}$, and $a_{i},(x_{1},\ldots,x_{n})\in I$:

    * –

$C(a_{i})=n^{aC}_{i}$, and

    * –

$C((x_{1},\ldots,x_{n})=x^{C}_{x_{i}}$ where $C\in X_{1}$.

It can be shown that $\mathcal{B}$ satisfies the aleatoric knowledge base, by
showing the semantics agree with the equations in $\Phi^{\mathcal{K}}$.

Conversely, given an aleatoric belief model $\mathcal{B}$ that satisfies the
aleatoric knowledge base $\mathcal{K}$, it can be shown that the set of
equations is satisfiable by induction. Beginning with the leaf nodes $X_{i}$
of the DAG, ranges for $x^{C}_{j}$ can be found for each $C\in X_{i}$, that
includes the values present in $\mathcal{B}$. Proceeding back up the DAG, the
other variables can be solved by noting that $e^{X_{i}X_{j}}{nm}$ and
$r^{X_{i}X_{j}}_{nm}$ provide the necessary degrees of freedom to guarantee a
solution exists.

The number of variables, inequalities and equalities in the system
$(\Lambda^{\mathcal{K}},\Psi^{\mathcal{K}},\Phi^{\mathcal{K}})$ is polynomial
in the size of $\mathcal{K}$, so determining if the system is satisfiable
reduces to $\exists\mathbb{R}$ (the satisfiability of existentially quantified
polynomial equations) which is in PSPACE. Theorem 4.8 follows from this
construction.

######  Theorem 4.8.

Given a simple aleatoric knowledge base
$\mathcal{K}=(\mathcal{A},\mathcal{T})$ where $\mathcal{T}$ is acyclic, it is
possible to determine if $\mathcal{K}$ is consistent with complexity PSPACE.

Finally, further reasoning tools can be inferred from [7], where a sound and
complete calculus is given for a propositional aleatoric logic, and another is
proposed for a modal extension. These calculi may be applied as term rewriting
systems to aid reasoning with aleatoric description logics.

##  5 Expressivity

This section presents a characterisation of aleatoric description logic as a
probability space of functional models introduced for $\mathcal{ALC}_{1}$. A
model of $\mathcal{ALC}_{1}$ gives a very simple ontological description of
the universe where at every individual every role is satisfied by precisely
one individual. The aleatoric belief models of $\mathrm{ADL}$ describe a
probability space of these simple descriptions, and the semantics of
$\mathrm{ADL}$ recursively define the likelihood of a formula holding in
models sampled from this probability space.

A probability space [13] is a tuple $(\Omega,\mathcal{F},\mathcal{P})$, where
$\Omega$ is a set, $\mathcal{F}$ is a $\sigma$-algebra over $\Omega$ (the
events), and $\mathcal{P}$ is a probability measure on $\mathcal{F}$ that is
countably additive. The formal definition is below:

######  Definition 5.1.

A probability space is a tuple $(\Omega,\mathcal{F},\mathcal{P})$, where:

  * •

$\Omega$ is a set.

  * •

$\mathcal{F}$ is a $\sigma$-algebra over $\mathcal{F}$, so
$\mathcal{F}\subset\wp(\Omega)$ such that:

    1. 1.

$\Omega\in\mathcal{F}$

    2. 2.

If $A\in\mathcal{F}$ then $\Omega-A\in\mathcal{F}$

    3. 3.

If $A_{0},A_{1},\ldots\in\mathcal{F}$ then
$\bigcup_{i=0}^{\omega}A_{i}\in\mathcal{F}$ (i.e. $\mathcal{F}$ is countably
additive).

  * •

$\mathcal{P}:\mathcal{F}\longrightarrow[0,1]$ is a probability measure on
$\mathcal{F}$ such that $\mathcal{P}(\Omega)=1$ and if
$A_{0},A_{1},\ldots\in\mathcal{F}$ are pairwise disjoint, then
$\mathcal{P}(\bigcup_{i=0}^{\omega}A_{i})=\sum_{i=0}^{\omega}\mathcal{P}(A_{i})$.

The probability space corresponding to an aleatoric belief model is
effectively the result of sampling interpretations of $\mathcal{ALC}_{1}$
(Definition 2.1) from the model.

######  Definition 5.2.

Given a pointed aleatoric belief model $\mathcal{B}_{i}=(I,r,\ell,i)$ defined
over a set of atomic concepts, $\mathrm{X}$, and roles, $\mathrm{R}$, we say
an interpretation of $\mathcal{ALC}_{1}$, $\mathcal{B}^{f}=(J,c,f)$, is a
sampling where:

  * •

$J=I^{+}$ is a set of finite non-empty words over $I$, every word in $J$
begins with $i$.

  * •

Given any $w\in I^{*}$, for all $wx\in J$, for all $\rho\in\mathrm{R}$, the
unique $w^{\prime}\in J$ where $(wx,w^{\prime})\in f(\rho)$ is such that
$w^{\prime}=wxy$ for some $y$ where $\rho(x,y)>0$

  * •

Given any $w\in I^{*}$ for all $wx\in J$, for all $A\in\mathrm{X}$
$wx\in\kappa(C)$ implies $\ell(x,A)>0$.

We let $\Omega^{\mathcal{B}_{i}}$ be the set of all samplings of
$\mathcal{B}_{i}$.

In the context of Section 3.2, each sampling in $\Omega^{\mathcal{B}}$
corresponds to a scenario where the outcome of each die has been
predetermined.

A $\sigma$-algebra over the probability space corresponds to a set of
formulas, $\mathcal{L}$ of $\mathcal{ALC}$, that is closed under countable
unions, closed under complementation, closed under subformulas, and includes
$\top$. Every formula $\alpha$ describes the set of interpretations
$\mathcal{B}^{f}_{i}$ in $\Omega^{\mathcal{B}_{i}}$, where
$\mathcal{B}^{f}_{i}\models\alpha$. This set of interpretations is referred to
as $\hat{\alpha}$. Given a set of formulas $\mathcal{L}$ closed under
countable unions, complementations and subformulas, let
$\hat{\mathcal{L}}=\\{\hat{\alpha}\ |\ \alpha\in\mathcal{L}\\}$ be the algebra
over $\Omega^{\mathcal{B}_{i}}$ generated by $\mathcal{L}$.

The probability measure, $\mathcal{P}{\mathcal{B}_{i}}$, over the algebra
$\hat{\mathcal{L}}$, is a function mapping an element $\hat{\alpha}$ to the
probability of sampling some interpretation, $\mathcal{B}^{f}_{i}$, from
$\mathcal{B}_{i}$, such that $\mathcal{B}^{f}_{i}\models\alpha$. The first
part of this definition requires mapping all formulas of $\mathcal{L}$ to
acyclic alternating automata [16].

######  Definition 5.3.

An acyclic alternating automaton is given with respect to a finite set of
atomic concepts $X^{\prime}$ and a finite set of roles $R^{\prime}$, and is
specified by a tuple
$\mathcal{A}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},s_{0})$
such that:

  * •

$S_{\exists}$ is a finite set of existential states.

  * •

$S_{\forall}$ is a finite set of universal states.

  * •

$\delta_{\exists}:S_{\exists}\times\Sigma\hookrightarrow\wp(S_{\forall})$ is a
partial function called the existential transition function.

  * •

$\delta_{\forall}:S_{\forall}\times R\hookrightarrow S_{\exists}$ is a partial
function called the universal transition function.

  * •

$s_{0}\in S_{\exists}$ is the initial state.

Additionally, the automaton must be acyclic so there is no sequence
$e_{0},\ell_{0},u_{0},\rho_{0},e_{1},\ell_{1},\ldots u_{n},\rho_{n}$ such that
$u_{i}\in\delta_{\exists}(e_{i},\ell_{i})$,
$e_{i+1}\in\delta_{\forall}(u_{i},\rho_{i})$ and
$e_{0}=\delta_{\forall}(u_{n},\rho_{n})$. The automaton $\mathcal{A}$ acts on
pointed interpretations of $\mathcal{ALC}_{1}$, $\mathcal{I}_{i}=(I,c,r,i)$ in
the form of a game $\mathcal{G}(\mathcal{A},\mathcal{I}_{i})$. The game is a
series of positions where every position is a pair in $(S_{\exists}\cup
S_{\forall})\times I$, and two players, $\exists$ and $\forall$, take turns
choosing the next position. The game starts at an initial position
$(s_{0},i)$. In a position $(s,i)$ where $s\in S_{\exists}$, player $\exists$
chooses $t\in\delta_{\exists}(s,\\{A\in X^{\prime}|\ i\in c(A)\\})$ (if it
exists), and the next position is $(t,i)$. In a position $(s,i)$ where $s\in
S_{\forall}$, player $\forall$ chooses some $\rho\in R^{\prime}$ and if
$\delta_{\forall}(s,\rho)$ exists, the next position becomes
$(\delta_{\forall}(s,\rho),j)$, where $(i,j)\in r(\rho)$. If at any position a
the player is unable to make a move because the transition function is not
defined, then that player loses the game. As the automaton is acyclic, every
game is determined, so given any automaton $\mathcal{A}$ and any pointed
$\mathcal{ALC}_{1}$ interpretation $\mathcal{I}$, either $\exists$ or
$\forall$ will have a winning strategy. If and only if $\exists$ has a winning
strategy in the game $\mathcal{G}(\mathcal{A},\mathcal{I}_{i})$, we say
$\mathcal{A}$ accepts $\mathcal{I}_{i}$.

The alternating automata give a computational representation of formulas of
$\mathcal{ALC}_{1}$, which are used to characterise a probability mass
function over the $\sigma$-algebra, $\hat{\mathcal{L}}$.

######  Lemma 5.4.

For every formula $\alpha$ of $\mathcal{ALC}_{1}$, there is an acyclic
alternating automaton that accepts exactly the pointed functional
interpretations $\mathcal{B}^{f}_{i}$, where
$\mathcal{B}^{f}_{i}\models\alpha$.

#### Proof:

A formula, $\alpha$, is first converted to positive normal form, $\alpha^{+}$
where negations are only applied to atoms, and $\sqcup$ disjunctions and
$\bot$ are added to the syntax. The positive normal form formulas are then
mapped to an acyclic alternating automaton, $\mathcal{A}^{\alpha}$ such that
the alternating automaton accept precisely the functional interpretations of
$\mathcal{ALC}_{1}$ that satisfy $\alpha$.

Given any formula $\alpha$ in positive normal form it is possible to construct
an acyclic alternating automaton, $\mathcal{A}^{\alpha}$, such that player
$\exists$ has a winning strategy in the game
$\mathcal{G}(\mathcal{A}^{\alpha},\mathcal{I}_{i})$ precisely when
$\mathcal{I}_{i}\models\alpha$. Let $X^{\prime}$ be the set of atomic concepts
appearing in $\alpha$, and $R^{\prime}$ be the set of roles that appear in
$\alpha$. A recursive construction is given below, with justifications for the
construction assuming a model $\mathcal{I}_{i}=(I,c,r,i)$. The non-trivial
constructions are below: $\beta_{1}\sqcap\beta_{2}$: Suppose
$\mathcal{A}^{\beta_{i}}=(S^{i}_{\exists},S^{i}_{\forall},\delta^{i}_{\forall},\delta^{i}_{\exists},s_{0}^{i})$,
for $i=1,2$. Then
$\mathcal{A}^{\beta_{1}\sqcap\beta_{2}}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},(s_{0}^{1},s_{0}^{2}))$,
where

  1. 1.

$S_{\exists}=S^{1}_{\exists}\cup S^{2}_{\exists}\cup\ S^{1}_{\exists}\times
S^{2}_{\exists}$

  2. 2.

$S_{\forall}=S^{1}_{\forall}\times S^{2}_{\forall}\cup S^{1}_{\forall}\cup
S^{2}_{\forall}$

  3. 3.

for $i=1,2,$ for all $s\in S^{i}_{\exists}$, for all $\ell\in\wp(X^{\prime})$,
$\delta_{\exists}(s,\ell)=\delta^{i}_{\exists}(s,\ell)$, for all
$(s,s^{\prime})\in S^{1}_{\exists}\times S^{2}_{\exists}$,
$\delta_{\exists}((s,s^{\prime}),\ell)=\delta^{1}_{\exists}(s,\ell)\times\delta^{2}_{\exists}(s^{\prime},\ell)$,
and
$\delta_{\exists}(\beta_{1}\sqcap\beta_{2},\ell)=\delta_{\exists}^{1}(s_{0}^{1},\ell)\times\delta_{\exists}^{2}(s_{0}^{2},\ell$

  4. 4.

for $i=1,2$, for all $s\in S^{i}_{\forall}$, for all $\rho\in R^{\prime}$,
$\delta_{\forall}(s,\rho)=\delta^{i}_{\forall}(s,\rho)$, for all
$(s,s^{\prime})\in S^{1}\times S^{2}_{\forall}$, for all $\rho\in R^{\prime}$,

    1. (a)

if $\delta^{1}_{\forall}(s,\rho)\neq\emptyset$ and
$\delta^{2}_{\forall}(s^{\prime},\rho)\neq\emptyset$ then
$\delta_{\forall}((s,s^{\prime}),\rho)=(\delta^{1}_{\forall}(s,\rho),\delta^{2}_{\forall}(s^{\prime},\rho))$,
and

    2. (b)

if $\delta^{1}_{\forall}(s,\rho)\neq\emptyset$ and
$\delta^{2}_{\forall}(s^{\prime},\rho)=\emptyset$ then
$\delta_{\forall}((s,s^{\prime}),\rho)=\delta^{1}_{\forall}(s,\rho)$, and

    3. (c)

if $\delta^{1}_{\forall}(s,\rho)=\emptyset$ and
$\delta^{2}_{\forall}(s^{\prime},\rho)\neq\emptyset$ then
$\delta_{\forall}((s,s^{\prime}),\rho)=\delta^{2}_{\forall}(s^{\prime},\rho)$.

The construction of the automaton is such that players $\exists$ and $\forall$
simultaneously play $\mathcal{G}(\mathcal{A}^{\beta_{1}},\mathcal{I}_{i})$ and
$\mathcal{G}(\mathcal{A^{\beta_{2}}},\mathcal{I}_{i})$. Player $\exists$ must
always play a move in both games, but player $\forall$ only needs to play a
move in one game for each role $\rho\in R^{\prime}$. If either
$\mathcal{I}_{i}\not\models\beta_{1}$ or
$\mathcal{I}_{i}\not\models\beta_{2}$, player $\forall$ has a winning strategy
in one game, and following that strategy will lead to a win in
$\mathcal{G}(\mathcal{A}^{\beta_{1}\sqcap\beta_{2}},\mathcal{I}_{i})$.
Conversely, if both $\mathcal{I}_{i}\models\beta_{1}$ and
$\mathcal{I}_{i}\models\beta_{2}$, then player exists has a winning strategy
in both games, and following these strategies simultaneously will lead to a
scenario where player $\forall$ cannot make a move.

$\alpha\sqcup\beta$: Suppose
$\mathcal{A}^{\beta_{i}}=(S^{i}_{\exists},S^{i}_{\forall},\delta^{i}_{\forall},\delta^{i}_{\exists},s_{0}^{i})$,
for $i=1,2$. Then
$\mathcal{A}^{\beta_{1}\sqcup\beta_{2}}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},\beta_{1}\sqcup\beta_{2})$,
where

  1. 1.

$S_{\exists}=S^{1}_{\exists}\cup
S^{2}_{\exists}\cup\\{\beta_{1}\sqcup\beta_{2}\\}$

  2. 2.

$S_{\forall}=S^{1}_{\forall}\cup S^{2}_{\forall}$

  3. 3.

for all $s\in S^{1}_{\exists}$, for all $\ell\in\wp(X^{\prime})$,
$\delta_{\exists}(s,\ell)=\delta^{1}_{\exists}(s,\ell)$, for all $s\in
S^{2}_{\exists}$, $\delta_{\exists}(s,\ell)=\delta^{2}_{\exists}(s,\ell)$, and
$\delta_{\exists}(\beta_{1}\sqcup\beta_{2},\ell)=\delta_{\exists}^{1}(s_{0}^{1},\ell)\cup\delta_{\exists}^{2}(s_{0}^{2},\ell)$.

  4. 4.

for all $s\in S^{1}_{\forall}$, for all $\rho\in R^{\prime}$,
$\delta_{\forall}(s,\rho)=\delta^{1}_{\forall}(s,\rho)$, and for all $s\in
S^{2}_{\forall}$, $\delta_{\forall}(s,\rho)=\delta^{2}_{\forall}(s,\rho)$.

In the game
$\mathcal{G}(\mathcal{A}^{\beta_{1}\sqcup\beta_{2}},\mathcal{I}_{i})$, player
$\exists$ is effectively able to choose whether to play the game
$\mathcal{G}(\mathcal{A}^{\beta_{1}},\mathcal{I}_{i})$ or
$\mathcal{G}(\mathcal{A}^{\beta_{2}},\mathcal{I}_{i})$. As player $\exists$
has a winning strategy in at least one of these games if and only if
$\mathcal{I}_{i}\models\beta_{1}\sqcup\beta_{2}$, the correspondence holds.

$\exists\rho.\beta$: Suppose
$\mathcal{A}^{\beta}=(S^{\beta}_{\exists},S^{\beta}_{\forall},\delta^{\beta}_{\forall},\delta^{\beta}_{\exists},s_{0}\beta)$.
Then
$\mathcal{A}^{\exists\rho.\beta}=(\wp(X^{\prime}),S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},\exists\rho.\beta)$,
where:

  1. 1.

$S_{\exists}=S^{\beta}_{\exists}\cup\\{\exists\rho_{\beta}\\}$

  2. 2.

$S_{\forall}=S^{\beta}_{\forall}\cup\\{\forall\rho_{\beta}\\}$

  3. 3.

for all $s\in S_{\exists}$, for all $\ell\in\wp(X^{\prime})$,
$\delta_{\exists}(s,\ell)=\delta^{\beta}_{\exists}(s,\ell)$, and
$\delta_{\exists}(\exists\rho_{\beta},\ell)=\\{\forall\rho\beta\\}$.

  4. 4.

for all $s\in S_{\forall},$ for all $\rho^{\prime}\in R^{\prime}$,
$\delta_{\forall}(s,\rho^{\prime})=\delta^{\beta}_{\forall}(s,\rho^{\prime})$
if $s\in S^{\beta}_{\forall}$, and
$\delta_{\forall}(\forall\rho.\beta,\rho^{\prime})$ is not defined if
$\rho\neq\rho^{\prime}$ and
$\delta_{\forall}(\forall\rho\beta,\rho)=s_{0}^{\beta}$

In this construction, the first move for both $\exists$ and $\forall$ are
effectively pre-determined. Player $\exists$ chooses $\forall\rho.\beta$, and
then if player $\forall$ chooses any role other than $\rho$, they immediately
lose. Therefore player $\forall$ chooses $\rho$, and as there is a single
$j\in I$ where $(i,j)\in r(\rho)$ the next position of the game is necessarily
$(s_{0}^{\beta},j)$. From there, the game is equivalent to the game
$\mathcal{G}(\mathcal{A}^{\beta},\mathcal{I}_{j})$, which, by induction, has a
winning strategy for $\exists$ if and only if $\mathcal{I}_{j}\models\beta$,
which in turn is equivalent to $\mathcal{I}_{i}\models\exists\rho\beta$, as
required.

As discussed above the constructions match the semantics of the associated
formulas. We can also see that the automata are acyclic, as the label of any
successor state is a subformula of the label of the current state. $\square$

To define a probability mass function, it is required that there is no
redundancy in the automaton, so we will assume that the automaton is
bisimulation minimal [16].

Given
$\mathcal{A}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},s_{0})$
is a minimal acyclic alternating automaton defined with respect to the set of
atomic concepts $X^{\prime}$ and the roles $R^{\prime}$, we characterise the
set of accepted models by a set of finite $X^{\prime}$-$R^{\prime}$-trees:

######  Definition 5.5.

Given the finite set of atomic concepts $X^{\prime}$ and the finite set of
roles $R^{\prime}$, and an acyclic alternating automaton
$\mathcal{A}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},s_{0})$,
a finite set of words $T\subset\wp(X^{\prime})(R^{\prime}\wp(X^{\prime}))^{*}$
is an accepted tree of $\mathcal{A}$ if there is some function
$\lambda:T\rightarrow S_{\exists}$ where:

  * •

there is some $Y\subseteq X^{\prime}$ for all $t\in T$, $t=Yw$, and
$\lambda(Y)=s_{0}$.

  * •

for all $\rho\in R^{\prime}$, for all $Y\subseteq X^{\prime}$, if $w\rho Y\in
T$, then $w\in T$.

  * •

for all $w\in T$, for all $\rho\in R^{\prime}$, for all $Y,Z\subseteq
X^{\prime}$ if $w\rho Y,w\rho Z\in T$, then $Y=Z$

  * •

for all $Y,Z\subseteq\wp(X^{\prime})$, for all $wY\in T$, for all $\rho\in
R^{\prime}$, if $\lambda(wY)=s$, and $\lambda(wY\rho Z)\in T$ then there is
some $s^{\prime}\in\delta_{\exists}(s,Y)$ such that $\lambda(wY\rho
Z)=\delta_{\forall}(s^{\prime},\rho)$.

  * •

for all $Y\subseteq\wp(X^{\prime})$, for all $wY\in T$, for all $\rho\in
R^{\prime}$, if $\lambda(wY)=s$, and $\forall Z\subseteq X^{\prime}$,
$\lambda(wY\rho Z)\notin T$ then there is some
$s^{\prime}\in\delta_{\exists}(s,Y)$ such that
$\delta_{\forall}(s^{\prime},\rho)$ is undefined.

The language recognised by $\mathcal{A}$ is the set $\mathcal{T}$ of accepted
trees of $\mathcal{A}$, $T$, where no proper subtree of $T$ is accepted by
$\mathcal{A}$.

The language recognised by $\mathcal{A}$ is effectively the prefix of all
interpretations that are accepted by $\mathcal{A}$, and gives a finite
representation of those interpretations.

A probability measure $\mathcal{P}^{\mathcal{B}_{i}}$ for the probability
space is defined as below.

######  Definition 5.6.

Let $\mathcal{B}_{i}=(I,r,\ell,i)$ be a pointed aleatoric belief model, and
let $\mathcal{L}$ be some set of $\mathcal{ALC}$ formulas defined over a
finite set of atomic concepts $X^{\prime}$ and a finite set of roles,
$R^{\prime}$, and suppose $\mathcal{L}$ is closed under countable unions,
complementations and subformulas, where $\top\in\mathcal{L}$. The probability
measure $\mathcal{P}^{\mathcal{B}_{i}}:\hat{\mathcal{L}}\longrightarrow[0,1]$
is defined such that:
$\mathcal{P}^{\mathcal{B}_{i}}(\hat{\alpha})=\sum_{T\in\mathcal{T}}P^{\mathcal{B}_{i}}(T)$,
where $\mathcal{T}$ is the language recognised by $\mathcal{A}^{\alpha}$ and
$P^{\mathcal{B}_{i}}:\mathcal{T}\rightarrow[0,1]$ is defined recursively as:

$\displaystyle P^{\mathcal{B}_{i}}(Y)$ $\displaystyle=$
$\displaystyle(\prod_{y\in Y}\ell(i,y)).(\prod_{y\in
X^{\prime}-Y}(1-\ell(i,y)))$ $\displaystyle{\rm where}\ Y\in\wp(X^{\prime})$
$\displaystyle P^{\mathcal{B}_{i}}(T)$ $\displaystyle=$ $\displaystyle
P^{\mathcal{B}_{i}}(Y).\sum_{\rho\in R^{\prime\prime},\ j\in
I}\rho(i,j).P^{\mathcal{B}_{j}}(T^{\rho})$ $\displaystyle{\rm where}\
T^{\rho}=\\{Y\rho T^{\rho}\ |\ \rho\in R^{\prime\prime}\subseteq
R^{\prime}\\}$

noting that $\sum_{x\in\emptyset}x=0$ and $\prod_{x\in\emptyset}x=1$.

The probability measure of the algebra element $\hat{\alpha}$, is the
probability of sampling a functional interpretation from $\mathcal{B}_{i}$
that the automaton $\mathcal{A}^{\alpha}$ will accept.

######  Lemma 5.7.

Let $\mathcal{B}_{i}$ be a pointed aleatoric belief model, and $\mathcal{L}$
be a set of $\mathcal{ALC}$ formulas closed under countable disjunctions,
complementations and subformulas. The tuple
$(\Omega^{\mathcal{B}_{i}},\hat{\mathcal{L}},\mathcal{P}^{\mathcal{B}_{i}})$
is a probability space.

#### Proof:

From the semantics of $\mathcal{ALC}_{1}$ it follows that $\hat{\mathcal{L}}$
is closed under complements and countable unions, and contains the entire
space $\Omega^{\mathcal{B}_{i}}=\hat{\top}$. It remains to show that
$\mathcal{P}^{\mathcal{B}_{i}}$ is a probability measure. From Definition 3.2
it follows that $\ell(i,y)\in[0,1]$ and $r(\rho,i)$ is a probability
distribution over $I$, so $\mathcal{P}^{\mathcal{B}_{i}}$ will be in the valid
range, $[0,1]$. As all formulas in $\mathcal{L}$ are finite, for the countable
additivity requirement it suffices to show that measure of any union of two
disjoint sets is equal to the sum of the measures of the sets. Again this
follows directly from the definition. If $\hat{\alpha}$ and $\hat{\beta}$ are
disjoint then the languages recognised by $\mathcal{A}^{\alpha}$ and
$\mathcal{A}^{\beta}$ will be disjoint since a common tree in the languages
would be able to generate an interpretation over which both automata had
accepting runs. Definition 5.6 describes the likelihood of an interpretation
being sampled from $\mathcal{B}_{i}$ that matches the recognised language of
an automaton, so the probability of sampling from either disjoint set is the
sum of the probabilities of sampling from each set. $\square$

Therefore, $\mathcal{B}_{i}$ describes a probability space,
$(\Omega^{\mathcal{B}_{i}},\mathcal{L},\mathcal{P}^{\mathcal{B}_{i}})$, of
$\mathcal{ALC}_{1}$ models for any set of formulas $\mathcal{L}$ closed under
countable disjunctions, complementations and subformulas. As such,
$\mathcal{P}^{\mathcal{B}_{i}}$ can be seen as a probability distribution of
ontological descriptions of a universe that is consistent with the semantic
interpretation of the formulas in $\mathcal{L}$.

The final part of this section shows that $\mathrm{ADL}$ characterises the
likelihood of formulas of $\mathcal{ALC}_{1}$ in this representation. It is
shown that for any $\mathcal{ALC}$ formula $\alpha$, there is a corresponding
$\mathrm{ADL}$ formula $\alpha^{*}$ such that
$\mathcal{P}^{\mathcal{B}_{i}}(\hat{\alpha})=\mathcal{B}_{i}(\alpha^{*})$.

######  Definition 5.8.

Let
$\mathcal{A}=(S_{\exists},S_{\forall},\delta_{\exists},\delta_{\forall},s_{0})$
be an acyclic alternating automaton defined over atomic concepts
$X^{\prime}=\\{x_{0},\ldots,x_{n}\\}$ and roles
$R^{\prime}=\\{\rho_{0},\ldots,\rho_{m}\\}$. For each state $s\in
S_{\exists}$, $\tau(s)$ is an $\mathrm{ADL}$ formula defined as follows:

$\tau(s)=\tau^{\emptyset}_{0}$ where for $Y\subseteq X^{\prime}$ and $i<n$
$\tau^{Y}_{i}=\left(x_{i}\mathbf{?}\tau^{Y\cup\\{x_{i}\\}}_{i+1}(s)\mathbf{:}\tau^{Y}_{i=1}\right)$
and
$\tau^{Y}_{n}=\left(x_{n}\mathbf{?}\Lambda(\delta_{\exists}(s,Y\cup\\{x\\}))\mathbf{:}\Lambda(\delta_{\exists}(s,Y))\right)$.

Given $S=\\{t_{0},\ldots,t_{k}\\}\subset S_{\forall}$,
$\Lambda(S)=\Lambda_{(0,0)}(\mu_{0})$ where for $(i,j)$ such that $i\leq m$
and $j\leq k$, and for
$\mu:\\{0,\ldots,m\\}\longrightarrow\mathcal{L}_{\mathrm{ADL}}$:

$\displaystyle\Lambda_{(i,j)}(\mu)$ $\displaystyle=$
$\displaystyle\left(\alpha\mathbf{?}\beta\mathbf{:}\gamma\right)\quad{\rm
where}$ $\displaystyle\alpha$ $\displaystyle=$
$\displaystyle[\rho]\left(\tau(\delta_{\forall}(t_{j},\rho_{i}))\\!\mid\\!\mu(\rho_{i})\right)$
$\displaystyle\beta$ $\displaystyle=$
$\displaystyle\Lambda_{(i+1,j)}(\mu^{[i\mapsto\mu(i)\sqcap\tau(\delta_{\forall}(t_{j},\rho_{i}))]})$
$\displaystyle\gamma$ $\displaystyle=$
$\displaystyle\Lambda_{(0,j+1)}(\mu^{[i\mapsto\mu(i)\sqcap\lnot\tau(\delta_{\forall}(t_{j},\rho_{i}))]})$

Here, $\mu_{0}(i)=\top$ for $i\leq m$, $\mu^{[i\mapsto\alpha]}(j)=\mu(j)$ for
all $j\neq i$, and $\mu^{[i\mapsto\alpha]}(i)=\alpha$. Also,
$\Lambda_{(n+1,j)}(\mu)=\top$ and $\Lambda_{(i,m+1)}=\bot$.

Let $\tau(\mathcal{A})=\tau(s_{0})$ and
$\alpha^{*}=\tau(\mathcal{A}^{\alpha})$.

Definition 5.8 motivates the syntactic structure of $\mathrm{ADL}$. For every
state $s\in S_{\exists}$, $\tau_{s}$ uses the if-then-else operator to build a
tree that evaluates each atomic concept exactly once, so the leaves of this
tree determine an element $Y\subseteq X^{\prime}$ that was sampled. Given $Y$
and $s$, the set $S=\delta_{\exists}(s,Y)$ of possible $S_{\forall}$
successors is computed, and then for each possible successor $t\in S$, for
every $\rho\in R^{\prime}$, $\Lambda(S)$ evaluates the likelihood of
$\tau(\delta_{\forall}(t,\rho))$ holding at the sampled $\rho$-successor of
the current state. Just as the if-then-else operator was used to ensure that
each concept was sampled only once, here the marginalisation operator is used
to require that each $\rho$-successor is effectively sampled only once. This
is done by using the function $\mu$ to retain what formula was evaluated
previously at the sampled $\rho$-successor, and using the marginalisation
operator to condition on that formula being true. While there is no guarantee
that the sampled $\rho$-successor will be exactly the same, the sample will be
taken from the same distribution so the average effect will be the same. The
if-then-else operator and the marginalisation operators are essential for
capturing these representations.

######  Lemma 5.9.

Let $\alpha$ be a formula of $\mathcal{ALC}$ $\mathcal{B}_{i}$ be an aleatoric
belief model, and $\mathcal{L}$ be a set of $\mathcal{ALC}$ formulas closed
under countable disjunctions, complementations and subformulas, where
$\alpha\in\mathcal{L}$. In the probability space
$(\Omega^{\mathcal{B}_{i}},\hat{\mathcal{L}},\mathcal{P}^{\mathcal{B}_{i}})$

$\mathcal{P}^{\mathcal{B}_{i}}(\hat{\alpha})=\mathcal{B}_{i}(\alpha^{*}).$

#### Proof:

(Sketch) The construction of $\alpha^{*}$ is such that every relation and
every concept in $\alpha$ is sampled once per individual mirroring the
probability measure $\mathcal{P}^{\mathcal{B}_{i}}$ (Definition 5.6). This can
be seen in the definition of $\tau(S)$ where $s\in S_{\exists}$: each atomic
concept is sampled, and the formula branches on the result, effectively
creating a tree where the leaves describe the set of atomic concepts sampled
to be true. For example, if $X^{\prime}=\\{x,y\\}$, then

$\tau(s)=\left(x\mathbf{?}\left(y\mathbf{?}\Lambda^{\\{xy\\}}_{s}\mathbf{:}\Lambda^{\\{x\\}}_{s}\right)\mathbf{:}\left(\\{y\\}\mathbf{?}\Lambda^{01}_{s}\mathbf{:}\Lambda^{\emptyset}_{s}\right)\right)$

where $\Lambda^{Y}_{s}=\Lambda(\delta_{\exists}(s,Y)$. Expanding the semantics
(Definition 3.3):

$\mathcal{B}_{i}(\tau_{s})=\sum\left\\{\begin{array}[]{l}\ell(i,x).\ell(i,y).\mathcal{B}_{i}(\Lambda^{\\{xy\\}}_{s})\\\
\ell(i,x).(1-\ell(i,y)).\mathcal{B}_{i}(\Lambda^{\\{x\\}}_{s})\\\
(1-\ell(i,x)).\ell(i,y).\mathcal{B}_{i}(\Lambda^{\\{y\\}}_{s})\\\
(1-\ell(i,x)).(1-\ell(i,y)).\mathcal{B}_{i}(\Lambda^{\emptyset}_{s})\end{array}\right\\}$

which agrees with the definition of $P^{\mathcal{B}_{i}}(Y)$ (Definition 5.6).

The definition of $\Lambda(S)$ recursively defines the probability of sampling
a set of $R^{\prime}$-successors that will ultimately be accepted by the
acyclic alternating automaton. It does this by checking the successors in
turn. In the definition of $\Lambda_{(0,0)}(\mu_{0})$, the
$\rho_{0}$-successor is sampled to test if the first $\delta_{\forall}$ state
($t_{0}$) will lead to an accepting run on that branch:

$\alpha=[\rho_{0}]\left(\tau(\delta_{\forall}(t_{0},\rho_{0}))\\!\mid\\!\top\right).$

When $\alpha$ holds, $\mu$ is updated to record that
$\tau(\delta_{\forall}(t_{0},\rho_{0}))$ was true at the $\rho_{0}$ successor,
and the formula $\Lambda_{(0,0)}^{\mu^{\prime}}$ then samples a $\rho_{1}$
successor to test if $t$ also leads to an accepting run on the $\rho_{1}$
branch. When $\alpha$ does not hold, the state $t_{0}$ will not lead to an
accepting run, so all other successors are ignored and attention moves to
$t_{1}$ and the process repeats. However, this time when a $\rho_{0}$
successor is sampled, it should be the same successor that was tested when
investigating $t_{0}$. All things being equal, any $\rho_{0}$-successor where
$\tau(\delta_{\forall}(t_{0},\rho_{)})$ does not hold is sufficient, so in
this case the $\rho_{1}$-successor is marginalised by the possibility:

$\gamma=[\rho_{0}]\left(\tau(\delta_{\forall}(t_{1},\rho_{0})\\!\mid\\!\lnot\tau(\delta_{\forall}(t_{0},\rho_{0}))\right).$

Expanding the fragment of semantics (Definition 3.3), assume that
$R^{\prime}=\\{\rho_{0}\\}$ and the set of $S_{\forall}$ successors are
$\\{t_{0},t_{1}\\}$ gives the following calculations:

$\displaystyle\mathcal{B}_{i}(\Lambda_{(0,0)}(\mu_{0}))$ $\displaystyle=$
$\displaystyle\mathcal{B}_{i}(\left([\rho_{0}]\left(\alpha_{0}\\!\mid\\!\top\right)\mathbf{?}\top\mathbf{:}[\rho_{0}]\left(\alpha_{1}\\!\mid\\!\lnot\alpha_{1}\right)\right))$
$\displaystyle=$
$\displaystyle\mathcal{B}_{i}(E_{\rho_{0}}\alpha_{0})+\mathcal{B}_{i}(\lnot
E_{\rho_{0}}\alpha_{0}).\frac{\sum_{j\in
I}\rho_{0}(i,j).\mathcal{B}_{i}(\alpha_{1}).\mathcal{B}_{i}(\lnot\alpha_{0})}{\sum_{j\in
I}\rho_{0}(i,j).\mathcal{B}_{i}(\lnot\alpha_{0})}$ $\displaystyle=$
$\displaystyle\mathcal{B}_{i}(E_{\rho_{0}}\alpha_{0})+\mathcal{B}_{i}(E_{\rho_{0}}(\alpha_{1}\sqcap\lnot\alpha_{0})),$

where $\alpha_{0}=\tau(\delta_{\forall}(t_{0},\rho_{0}))$ and
$\alpha_{1}=\tau(\delta_{\forall}(t_{1},\rho_{0}))$. Therefore, each
probability of an accepting run is summed to give the probability of sampling
a functional model recognised by the automaton, as in Definition 5.6.
$\square$

The following theorem is a direct consequence of Lemmas 5.4, 5.7 and 5.9

######  Theorem 5.10.

Given a formula $\alpha$ of $\mathcal{ALC}$ and an aleatoric belief model
$\mathcal{B}_{i}$, there exists: a formula $\alpha^{*}$ that is logically
equivalent to $\alpha$ in $\mathcal{ALC}$; and probability space
$(\Omega^{\mathcal{B}_{i}},\mathcal{F},\mathcal{P}^{\mathcal{B}_{i}})$ where:
$\Omega^{\mathcal{B}_{i}}$ is a set of functional $\mathcal{ALC}$ models;
$\mathcal{F}$ is an algebra over $\Omega^{\mathcal{B}_{i}}$ consisting of an
element $\hat{\beta}$ for every $\mathcal{ALC}$ formula $\beta$; and
$\mathcal{P}^{\mathcal{B}_{i}}$ is a probability measure on $\mathcal{F}$
derived from $\mathcal{B}_{i}$. This probability space is such that
$\mathcal{P}^{\mathcal{B}_{i}}(\hat{\alpha})=\mathcal{B}_{i}(\alpha^{*})$.

Note, this correspondence only goes in one direction since the translation
from $\mathcal{ALC}$ to $\mathrm{ADL}$ is not surjective. A reverse
translation is not possible as $\mathrm{ADL}$ can represent properties not
expressible by $\mathcal{ALC}$: for example $C\sqcap C\neq C$ in
$\mathrm{ADL}$. However, it is possible to give a correctness preserving
translation from $\mathcal{ALC}$ to $\mathrm{ADL}$, and [7] presents a
correctness proof for the modal case.

Finally a direct encoding of $\mathcal{ALC}$ may be given in $\mathrm{ADL}$ by
projecting all concept probabilities to 0 or 1, and using a uniform
distribution to simulate quantification over roles. This construction is
sketched below (see [7] for a correctness proof in the modal case).

Let $\mathcal{I}_{i}=(I,c,r^{\prime},i)$ be an interpretation of
$\mathcal{ALC}$, where $I$ is finite, and define
$\mathcal{B}^{\mathcal{I}}_{i}=(I,r,\ell,i)$ to be the pointed aleatoric
belief model, where

  * •

$\rho(i,j)=\frac{1}{|\\{k\in I\ |\ (i,k)\in r^{\prime}(\rho))\\}|}$ if
$(i,j)\in r^{\prime}(\rho)$ and $0$ otherwise.

  * •

$\ell(i,A)=1$ if $i\in c(A)$ and $0$ otherwise.

Once atom distributions have been mapped to Booleans and role distributions
have been made uniform, it is straightforward to show that the abbreviations
in Table 1 preserve their meaning so $\mathcal{I}_{i}\models\alpha$ if and
only if $\mathcal{B}^{\mathcal{I}}_{i}(\alpha)=1$.

##  6 Learning

An aleatoric belief model describes an agent’s beliefs and prior assumptions
and the agent may update these beliefs based on observations, via Bayesian
conditioning. This section will introduce two learning mechanisms, role
learning and concept learning whereby an agent may update the distribution of
individuals fulfilling a role, and also update the aleatoric probabilities
associated with an atomic concept at an individual. These mechanisms are
unique to $\mathrm{ADL}$ and provides a compelling advantage over alternative
probabilistic description logics [4, 18, 8, 26, 22].

In this sense, given a consistent aleatoric belief set, an aleatoric belief
model acts can be chosen as a Bayesian prior (for example, by assigning a
uniform prior to undeclared probabilities). Then observations of individuals,
concepts, and roles can be used to compute posterior likelihoods, which update
the aleatoric belief model. Therefore, even a quite basic belief model can be
refined over time to detect and learn subtle relationships between concepts
and individuals.

The two learning mechanisms discussed here are role learning and concept
learning. In this setting, it is assumed that the agent has prior beliefs, and
these beliefs involve some uncertainty (modelled aleatorically). The agent
also has an observation, which is a formula of $\mathrm{ADL}$. While
observation can be considered a fact, and not subject to uncertainty, it is
also able to inform the agent about there own beliefs, via Bayesian updating.

Consider the example from Subsection 3.4, with Hector, Igor, and Julia, each
of whom maybe infected with a virus or not. Suppose that this model is a
representation of Hector’s beliefs, and also, that Hector is informed via a
contact-tracing exercise that they have come into contact with an infected
person. This information alone, allows Hector to refine the belief model,
through role learning

###  6.1 Role learning

Role learning refines the probability distribution associated with a role
$\rho$. For a pointed aleatoric belief model, $\mathcal{B}_{i}=(I,r,\ell,i)$,
for every $j\in I$, $\rho(i,j)$ is the prior probability that $j$ fulfils the
role of $\rho$ for $i$. Given an observation which is an $\mathrm{ADL}$
formula of the form $[\rho]\left(\alpha\\!\mid\\!\top\right)$,
$\mathcal{B}_{j}(\alpha)$ is the probability of this observation holding,
given $j$ fulfils the role of $\rho$ for $i$. Via Bayes’ rule, it follows that
the probability of $j$ fulfilling the role of $\rho$ for $i$, given the
observation is:

$\rho^{\prime}(i,j)=\frac{\rho(i,j)\cdot\mathcal{B}_{j}(\alpha)}{\mathcal{B}_{i}([\rho]\left(\alpha\\!\mid\\!\top\right))}$

(the prior probability of $j$ is multiplied by the probability of $\alpha$
given $j$, divided by the probability of $\alpha$).

######  Definition 6.1.

Let $\mathcal{B}_{i}=(I,r,\ell,i)$ be an aleatoric belief model, and
$\phi=[\rho]\left(\alpha\\!\mid\\!\beta\right)$ an observation, made at $i$.
The $\phi$-update of $\mathcal{B}_{i}$ is the aleatoric belief model
$\mathcal{B}^{\phi}_{i}=(I,r^{i,\alpha},\ell,i)$, where for all
$\rho^{\prime}\neq\rho$ and $j\neq i$, $r^{i,\phi}(\rho^{\prime},j)=r(\rho,j)$
and for all $j\in I$

$r^{i,\phi}(\rho,i)(j)=\frac{\rho(i,j)\cdot\mathcal{B}_{j}(\alpha)}{\mathcal{B}_{i}([\rho]\left(\alpha\\!\mid\\!\beta\right))}.$

Thus an agent with an aleatoric model of the world may update their epistemic
uncertainty of the distribution of roles, via Bayesian conditioning. The
$\phi$-update of $\mathcal{B}_{i}$ is the agent’s posterior model of the
world.

Given the example in Subsection 3.4, suppose that Hector’s belief model is
$\mathcal{B}=(I,r,\ell,i)$, and Hector is informed that the contact has tested
positive for the virus. Hector is also informed that the test used has a 10%
false positive rate, so Hector’s belief model now includes an atomic concept
$\mathit{FP}$ that is 0.1 everywhere. Let
$\phi=[c]\left(\left(FP\mathbf{?}\top\mathbf{:}V\right)\\!\mid\\!\top\right)$
and then the $\phi$-update of $\mathcal{B}_{\mathtt{H_{0}}}$ is computed by:

$r^{\mathtt{H_{0}},\phi}(c,\mathtt{H_{0}})(j)=\frac{c(i,j)\cdot(0.1+0.9\cdot\mathcal{B}_{j}(V)}{\mathcal{B}_{\mathtt{H_{0}}}([c]\left(\left(FP\mathbf{?}\top\mathbf{:}V\right)\\!\mid\\!\top\right))}.$

Substituting in the values from Table 2, Hector is able to discount the
possible individuals without a virus and condition the distribution for
$contact$ accordingly. The $\phi$-update of $\mathcal{B}_{\mathtt{H_{0}}}$ is
represented in Figure 2.

$\begin{array}[]{c}\mathtt{H_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.1\end{array}$ $\begin{array}[]{c}\mathtt{H_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.6\end{array}$
$\begin{array}[]{c}\mathtt{I_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.3\end{array}$ $\begin{array}[]{c}\mathtt{I_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.8\end{array}$
$\begin{array}[]{c}\mathtt{J_{0}}\\\ {\mathit{V}}:0.0\\\
{\mathit{F}}:0.2\end{array}$ $\begin{array}[]{c}\mathtt{J_{1}}\\\
{\mathit{V}}:1.0\\\ {\mathit{F}}:0.9\end{array}$
$\mathtt{id}$0.10.9$\mathtt{id}$$\mathbf{0.1}$$\mathbf{0.9}$$\mathtt{id}$$\mathbf{0.05}$$\mathbf{0.95}$$\mathtt{c}$0.4$\mathbf{0.25}$$\mathtt{c}$0.60.6$\mathtt{c}$$\mathbf{0.75}$0.4

Figure 2: The $\phi$-update of the aleatoric belief model in Figure 1, after
Hector is told a contact has tested positive for the virus. The updated values
are bold.

It may seem odd that we “observe” a marginalised formula, as there is non
concept of conditional probability in a single observation. However this makes
sense when it is interpreted as an instance of selection bias. For example,
suppose that a citizen presents at a doctors surgery, and some test suggest
the citizen is infected with influenza, which supports the theory that there
is an influenza epidemic (i.e. we observe $E_{\mathit{citizen}}\mathit{Flu}$).
However, the observation is not of a random person, but rather of a person who
elected to attend a doctors surgery, and therefore the actual observation is
more likely the likelihood the citizen has flu, given that they presented at
the surgery:
$[\mathit{citizen}]\left(\mathit{Flu}\\!\mid\\!\mathit{sympt}\right)$.

###  6.2 Concept learning

Role learning is a natural application of Bayes’ law since the learning is
applied to a probability distribution of possible individuals. However, the
probabilities of atomic concepts are modelled as dice, and hence independent
of all other variables beyond the possible individual. This means we gain no
additional information from applying Bayes’ law. If it was possible to observe
atomic concepts directly (and often) it would be simple to refine a
statistical model of the probabilities. Observations in $\mathrm{ADL}$ are
complex formulas, so it is preferable to find a more general solution.

Concept learning addresses these issues by introducing new possible
individuals in such a way that they do not affect any expected values for
named individuals but with variations in the aleatoric probability of
concepts, which may then be learnt via role learning, given arbitrary
observations.

The key to this update is the following observation. Suppose that you are
playing a game where you must roll a one on a biased die, and you do not know
the bias. The game master offers you a choice you can either roll once as
usual, or alternatively you may flip a fair coin. If the coin lands heads you
have two chances to roll a one, but if the coin lands tails, you must roll two
ones in a row. Both these choices have exactly the same chance of success. In
the first instance you have a $p$ chance of winning, and in the second
instance you have a $\frac{1-(1-p)^{2}+p^{2}}{2}=p$ chance of success.
However, in the second instance there are two alternatives, one with an
increased chance of success and one with a diminished chance of success. These
two alternatives may then be subjected to role learning.

######  Definition 6.2.

Given a pointed aleatoric belief model $\mathcal{B}_{i}=(I,r,\ell,i)$ and some
concept to refine, $A\in X$, the $A$-extension of $\mathcal{B}_{i}$ is the
aleatoric belief model
$\mathcal{B}_{i}^{A}=(I^{\prime},r^{\prime},\ell^{\prime},i)$, where:

  1. 1.

$I^{\prime}=I\cup\\{i^{*}\\}$

  2. 2.

For all $j\in I$, for all $\rho\in\mathrm{R}$,
$r^{\prime}(\rho)(j,i)=r^{\prime}(\rho)(j,i^{*})=r(\rho)(j,i)/2$, and
$r^{\prime}(\rho)(i,j)=r^{\prime}(\rho)(i^{*},j)=\rho(i,j)$ where $j\neq i$.

  3. 3.

For all $j\in I$, for all $B\in\mathrm{X}$,

    1. (a)

$\ell^{\prime}(j,B)=\ell(j,B)$, if $B\neq A$ or $j\neq i$,

    2. (b)

where $B\neq A$, $\ell^{\prime}(i^{*},B)=\ell(i,B)$,

    3. (c)

$\ell^{\prime}(i^{*},A)=\ell(i,A)^{2}$, and

    4. (d)

$\ell^{\prime}(i,A)=2\ell(i,A)-\ell(i,A)^{2}$

Note that in the $A$-extension of $\mathcal{B}_{i}$, $i$ and $i^{*}$ will be
related by $\mathtt{id}$, and are identical except for the probability
assigned to $A$. This intuition can be formalised via the probability spaces
of Lemma 5.7.

######  Lemma 6.3.

Let $\mathcal{B}_{i}=(I,r,\ell,i)$ be a pointed aleatoric belief model, and
let $A\in X$. Given $\mathcal{C}=\mathcal{B}^{A}_{i}$ and
$\mathcal{D}=\mathcal{B}^{A}_{i^{\prime}}$, and a set of $\mathcal{ALC}$
formulas, $\mathcal{L}$ as in Definition 5.6, let
$(\Omega,\hat{\mathcal{L}},\mathcal{P})$ be a probability space defined by
$\Omega=\Omega^{\mathcal{C}}\cup\Omega^{\mathcal{D}}$, and for all
$\hat{\alpha}\in\hat{\mathcal{L}}$,

$\mathcal{P}(\hat{\alpha})=\frac{\mathcal{P}^{\mathcal{C}}(\hat{\alpha})+\mathcal{P}^{\mathcal{D}}(\hat{\alpha})}{2}.$

Then $(\Omega,\hat{\mathcal{L}},\mathcal{P})$ is a probability space, and
furthermore, for all $\hat{\alpha}\in\hat{\mathcal{L}}$,
$\mathcal{P}^{\mathcal{B}_{i}}(\hat{\alpha})=\mathcal{P}(\hat{\alpha})$.

This follows from the reasoning above, and it is straightforward to check the
conditions of a probability space are met.

In practice this operation can be applied many times to learn correlations
between different concepts. However, performing these operations across all
individuals and a set of $n$ atomic concepts, will lead to a $2^{n}$ factor
increase in the size of the model so once the distribution of a concept has
been refined the two possible individuals $i$ and $i^{*}$ can be combined back
into a single individual by taking the sum of the probabilities of their
concepts and roles, weighted by the learnt distribution for $\mathtt{id}$.

In the example of Subsection 3.4, suppose that the assessment that the
likelihood of Hector having a fever is to be reassessed, based on the
observation (or possibly erroneous belief) that Hector would have a fever if
and only if Hector’s contact had a fever. A new world $\mathtt{H_{0}}$ is
replaced by $\mathtt{H_{0}}^{1}$ and $\mathtt{H_{0}}^{2}$ where
$\mathtt{H_{0}}^{1}(F)=2\mathtt{H_{0}}(F)-\mathtt{H_{0}}(f)^{2}=0.84$, and
$\mathtt{H_{0}}^{2}(F)=\mathtt{H_{0}}(F)^{2}=0.36$. The probabilities are then
updated via role learning over $\mathtt{id}$, given the observation
$\phi=E_{\mathtt{id}}{\left(F\mathbf{?}E_{c}{F}\mathbf{:}E_{c}\lnot
F\right)}$, where the relevant fragment of the aleatoric belief model is shown
in Figure 3. Note, the model has been revised to make the example clearer.

$\begin{array}[]{c}\mathtt{H_{0}}\\\ {\mathit{F}}:0.6\end{array}$
$\begin{array}[]{c}\mathtt{J_{1}}\\\ {\mathit{F}}:0.2\end{array}$
$\begin{array}[]{c}\mathtt{J_{0}}\\\ {\mathit{F}}:0.9\end{array}$
0.80.2$\begin{array}[]{c}\mathtt{H_{0}}\\\ {\mathit{F}}:0.84\end{array}$
$\begin{array}[]{c}\mathtt{H_{0}}^{*}\\\ {\mathit{F}}:0.36\end{array}$
$\begin{array}[]{c}\mathtt{H_{1}}\\\ {\mathit{F}}:0.2\end{array}$
$\begin{array}[]{c}\mathtt{J_{0}}\\\ {\mathit{F}}:0.9\end{array}$ 0.5
(0.42)0.5 (0.58)0.20.8

Figure 3: Concept learning applied to the aleatoric belief model in Figure 1,
where Hector applies the belief that he would only have a fever if and only if
a contact had a fever. The model on the left is the $F$-extension, and the
probabilities in brackets are the values after role learning has been applied
to $\mathtt{id}$.

In the individuals $\mathtt{H_{0}}$ and $\mathtt{H_{0}}^{*}$, role learning
can be applied over $\mathtt{id}$. The probability of $\phi$ in
$\mathtt{H_{0}}$ is approximately $0.4$ and the probability of $\phi$ in
$\mathtt{H_{0}}^{*}$ is approximately $0.55$, so after role learning has been
applied to $\mathtt{id}$ the probability of $\mathtt{H_{0}}$ is 0.42 and the
probability of $\mathtt{H_{0}}^{*}$ is 0.58. Finally, aggregating
$\mathtt{H_{0}}$ and $\mathtt{H_{0}}^{*}$ into a single node by taking
weighted sums of the likelihoods gives the probability of $F$ to be 0.56.

This example also demonstrates how $\mathrm{ADL}$ can work with complex
beliefs, such as $\phi$.

##  7 Related work

There is a substantial amount of work on logics for reasoning about
uncertainty [10], including [15, 14, 27, 19], and going back to the works of
Ramsey [24], Carnap [3] and de Finetti [5].

Probabilistic modal logics have also been studied extensively [10, 15, 14].
The approach to reasoning about probabilities used here is to have explicit
probabilities in the syntax of the logic. Therefore, these logics can express
propositions such as the chance of rain in 68%, or it is twice as likely to
rain as it is to snow. These propositions are either true or false, so they
reason about probabilities, rather than reasoning probabilistically. Axioms
and model-checking procedures have been provided for these logics, but they
tend to be hard to apply in practise, since the probabilities are explicit and
hard to calculate. By contrast, an aleatoric proposition would be something
like rain-today, which could be evaluated as 0.68, but it is an implicit value
that may vary with an agent’s experience.

Markov Logic Networks [25] (generalising Bayesian networks and Markov
networks) address a similar problem of providing a logical interface to
machine learning methods. These approaches attach a probabilistic
interpretation to formulas in a fragment of first order logic, rather than
providing a probabilistic variation of first order logic operators. Therefore,
whilst providing some of the benefits of logical approaches in a machine
learning context, there is only a weak coupling between first order deduction
and the probabilistic semantics.

There is some commonality in purpose with probabilistic logic programming [17,
6]. However, the concepts are constrained to be Horn clauses, where atomic
formula are mutually independent.

There is a growing body of work addressing the need for probabilistic
reasoning in knowledge bases. In [11], an inductive reasoning approach is
applied to include probabilities with rules; in [8], a subjective Bayesian
approach is proposed to describe the probabilities associated with a concept
or role holding; and Lukasiewicz and Straccia [18] have proposed a method to
include vagueness (or fuzzy concepts [28]) in descriptions logics.
Probabilistic extensions of description logics have also been proposed by
Rigguzzi et al [26] and Pozzato [22]. These approaches extend knowledge bases
to include probabilistic assertions and axioms, and provide an extended syntax
for querying probability thresholds. Some work on learning parameters and
structure of knowledge bases via probabilistic description logics has been
done, including Ceylan and Penaloza [4], who have proposed a Bayesian
Description Logic that combines a basic description logic framework with
Bayesian networks [21] for representing uncertainty about facts, and Ochoa
Luna et al [20] who applied statistical methods to estimate the most likely
configuration of a knowledge base.

These approaches are very different to the work presented here, as
probabilities are not propagated through the roles, and they do not permit
learning based on the observation of complex propositions.

##  8 Conclusion

This paper has introduced a novel approach for representing uncertain
knowledge and beliefs. Generalising the description logic $\mathcal{ALC}$, the
aleatoric description logic is able to represent complex concepts as
independent aleatoric events. The events are contingent on possible
individuals so they give a subjective Bayesian interpretation of knowledge
bases. This paper has also given computational reasoning methods for aleatoric
knowledge bases, and shown how aleatoric description logic corresponds to a
probability space of functional $\mathcal{ALC}$ models. Importantly, the
syntax of $\mathrm{ADL}$ does not include explicit probabilities so these do
not need to be known a priori, and can be learnt and integrated into the
aleatoric belief set based on observations. The aleatoric concepts and roles
enable a simple learning framework where agents are able to update their
beliefs based on the observations of complex propositions.

## References

  * [1] Franz Baader, Diego Calvanese, Deborah McGuinness, Peter Patel-Schneider, Daniele Nardi, et al.  The description logic handbook: Theory, implementation and applications.  Cambridge university press, 2003.
  * [2] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.  Data Complexity of Query Answering in Description Logics.  Artificial Intelligence, 195:335–360, 2013.
  * [3] Rudolf Carnap.  On Inductive Logic.  Philosophy of science, 12(2):72–97, 1945.
  * [4] Ismail Ilkan Ceylan and Rafael Penaloza.  The Bayesian Description Logic $\mathcal{BEL}$.  In International Joint Conference on Automated Reasoning, pages 480–494. Springer, 2014.
  * [5] Bruno De Finetti.  Theory of Probability: A critical introductory treatment.  John Wiley & Sons, 1970.
  * [6] Luc De Raedt, Angelika Kimmig, and Hannu Toivonen.  Problog: A probabilistic prolog and its application in link discovery.  In IJCAI, volume 7, pages 2462–2467. Hyderabad, 2007.
  * [7] Tim French, Andrew Gozzard, and Mark Reynolds.  A Modal Aleatoric Calculus for Probabilistic Reasoning.  In Indian Conference on Logic and Its Applications, pages 52–63. Springer, 2019.
  * [8] Víctor Gutiérrez-Basulto, Jean Christoph Jung, Carsten Lutz, and Lutz Schröder.  Probabilistic Description Logics for Subjective Uncertainty.  Journal of Artificial Intelligence Research, 58:1–66, 2017.
  * [9] Gary Gygax and David Cook.  The Dungeon Master Guide, No. 2100, 2nd Edition (Advanced Dungeons and Dragons).  TSR, Inc, 1989.
  * [10] J.Y. Halpern.  Reasoning about Uncertainty.  MIT Press, Cambridge MA, 2003.
  * [11] Jochen Heinsohn.  Probabilistic Description Logics.  In Uncertainty Proceedings 1994, pages 311–318. Elsevier, 1994\.
  * [12] Audun Jøsang.  Subjective logic.  Springer, 2016.
  * [13] Andreĭ Nikolaevich Kolmogorov and Albert T Bharucha-Reid.  Foundations of the Theory of Probability: Second English Edition.  Courier Dover Publications, 2018.
  * [14] Barteld P Kooi.  Probabilistic Dynamic Epistemic Logic.  Journal of Logic, Language and Information, 12(4):381–408, 2003\.
  * [15] Dexter Kozen.  A Probabilistic PDL.  Journal of Computer and System Sciences, 30(2):162–178, 1985.
  * [16] Christof Loding and Wolfgang Thomas.  Alternating automata and logics over infinite words.  In IFIP International Conference on Theoretical Computer Science, pages 521–535. Springer, 2000.
  * [17] Thomas Lukasiewicz.  Probabilistic logic programming.  In ECAI, pages 388–392, 1998.
  * [18] Thomas Lukasiewicz and Umberto Straccia.  Managing Uncertainty and Vagueness in Description Logics for the Semantic Web.  Web Semantics: Science, Services and Agents on the World Wide Web, 6(4):291–308, 2008.
  * [19] Nils J Nilsson.  Probabilistic Logic.  Artificial intelligence, 28(1):71–87, 1986.
  * [20] José Eduardo Ochoa-Luna, Kate Revoredo, and Fábio Gagliardi Cozman.  Learning probabilistic description logics: A framework and algorithms.  In Mexican International Conference on Artificial Intelligence, pages 28–39. Springer, 2011.
  * [21] Judea Pearl.  Causality: Models, Reasoning, and Inference.  Econometric Theory, 19(675-685):46, 2003.
  * [22] Gian Luca Pozzato.  Typicalities and probabilities of exceptions in nonmotonic description logics.  International Journal of Approximate Reasoning, 107:81–100, 2019\.
  * [23] Frank P Ramsey.  Truth and probability (1926).  The Foundations of Mathematics and other Logical Essays, pages 156–198, 1931.
  * [24] Frank P Ramsey.  Truth and Probability.  In Readings in Formal Epistemology, pages 21–45. Springer, 2016\.
  * [25] Matthew Richardson and Pedro Domingos.  Markov logic networks.  Machine learning, 62(1-2):107–136, 2006.
  * [26] Fabrizio Riguzzi, Elena Bellodi, Evelina Lamma, and Riccardo Zese.  Probabilistic description logics under the distribution semantics.  Semantic Web, 6(5):477–501, 2015.
  * [27] Johan Van Benthem, Jelle Gerbrandy, and Barteld Kooi.  Dynamic Update with Probabilities.  Studia Logica, 93(1):67, 2009.
  * [28] Lotfi A Zadeh.  Fuzzy Sets.  In Fuzzy Sets, Fuzzy Logic, And Fuzzy Systems: Selected Papers by Lotfi A Zadeh, pages 394–432. World Scientific, 1996.