=Paper=
{{Paper
|id=Vol-2211/paper-23
|storemode=property
|title=Cutting Diamonds: Temporal DLs with Probabilistic Distributions over Data
|pdfUrl=https://ceur-ws.org/Vol-2211/paper-23.pdf
|volume=Vol-2211
|authors=Alisa Kovtunova,Rafael Peñaloza
|dblpUrl=https://dblp.org/rec/conf/dlog/KovtunovaP18
}}
==Cutting Diamonds: Temporal DLs with Probabilistic Distributions over Data==
https://ceur-ws.org/Vol-2211/paper-23.pdf
Cutting Diamonds
Temporal DLs with Probabilistic Distributions over Data
Alisa Kovtunova and Rafael Peñaloza
KRDB Research Centre, Free University of Bozen-Bolzano, Italy.
{alisa.kovtunova,rafael.penaloza}@unibz.it
Abstract. Recent work has studied a probabilistic extension of the tem-
poral logic LTL that refines the eventuality (or diamond) constructor
with a probability distribution on when will this eventuality be satisfied.
In this paper, we adapt this notion to a well established temporal exten-
sion of DL-Lite, allowing the new probabilistic constructor only in the
ABox assertions. We investigate the satisfiability problem of this new
temporal DL over equiparametric geometric distributions.
1 Introduction
Combinations of DLs with temporal formalisms have been widely investigated
since the early work of [20]; we refer the reader to [2,8,9,16] for detailed surveys
of the area. Despite the different visions of the problem presented, logical theories
that encode a domain of interest are always represented by factual statements.
However, speaking about the future by itself can imply (probabilistic) uncer-
tainty.
For example, insurance companies estimate the probability of the insured
event in the duration period of the policy based in a number of factors; e.g.,
for a life insurance, they consider health condition, number of children, habits,
sun radiation in home region, etc. This defines the extent of monthly payment
for a customer. If one uses a classical temporal DL, one can only express that
everyone dies (LivingBeing v 3Dead), and miss the golden goose of insurers.
There is also a large pool of proposals for probabilistic DLs, e.g., [10, 17–19],
that differ widely in many fundamental aspects, like the way in which prob-
abilities are used, in the syntax, in the chosen semantics, and in the possible
application. We refer to [13] for a (now slightly outdated) survey. There are two
main views of probability [11], statistical and subjective. While the statistical
view considers a probability distribution over a domain that specifies the prob-
ability for an individual in the domain to be randomly picked, we choose the
subjective view, which specifies the probability distribution over a set of possi-
ble worlds. In our case, a world would be a possible evolution of a system; that is,
a standard temporal DL interpretation. The authors of [10] argue the subjective
semantics provides an appropriate modelling for probabilistic statements about
individuals, e.g., the statement “there’s at least 80% chance of not having an
earthquake tomorrow” implies that an earthquake will either occur or will not
occur. Thus, in the set of possible worlds, there are some structures in which an
earthquake happens and others in which it does not. This type of uncertainty
can also be called epistemic, because it regards probabilities as the degree of our
belief.
This paper presents the language TLD-Lite, which, to the best of our knowl-
edge, is a first probabilistic extension of temporal description logics and aims
at closing the gap between probabilistic and temporal extensions of lightweight
DLs. We propose a new view on one of the pillars of the linear temporal logic
LTL, the eventuality (or diamond) constructor, which expresses that some prop-
erty will hold at some point in the future. The specification of the diamond
operator is nondeterministic and, thus, can be too rough; indeed, with the basis
of actual life experience one often has an idea—albeit uncertain—about when
the property may hold. Employing basic notions from statistical analyses, we
combine an ontology of a well established temporal extension of DL-Lite pro-
posed in [5] with temporal data specified by the geometric distribution with
parameter p ≥ 12 .
This logic allows us to reason over time dimension with uncertain knowledge.
For example, if one builds an earthquake-resistant house, one wants to be sure an
earthquake does not ruin it before building bricks and concrete blocks are prop-
erly reinforced. Also, if local hospitals take vacation on Sundays, an earthquake
in the construction camp this day of the week inflicts heavier losses.
For the resulting temporal lightweight description logic with distributions,
aka TLD-Lite, we present the formal semantics underlying the language, intro-
duce the probabilistic formalism realised by means of the probabilistic constraint
⬖δ , called the distribution eventuality, and investigate the satisfiability problem.
Consistency can be checked by a deterministic algorithm using exponential space
in the size of input. An open question is whether the result can be improved
to match the coNExpTime upper bound obtained in [14] for the propositional
temporal formula with only one instance of the distribution eventuality ⬖δ . This
new refined diamond constructor includes a discrete probability distribution δ
that can be used to specify the likelihood of observing the property of interest,
for the first time, at each possible point in time.
Due to space restrictions, longer proofs of Lemmas 8 and 11 are deferred to
the full version [15].
2 Preliminaries
We briefly introduce the basics of probability theory and temporal extensions of
description logics.
2.1 Probability Theory
We start by providing the basic notions of probability needed for this paper. For
a deeper study on probabilities, we refer the interested reader to [6]. Let Ω be a
set called the sample space. A σ-algebra over Ω is a class F of subsets of Ω that
contains the empty set, and is closed under complements and under countable
unions. A probability measure is a function µ : F → [0, 1] such that µ(Ω) = 1,
and for Sany countable collection of pairwise disjoint sets Ei ∈ F, i ≥ R1, it holds
∞ P∞
that µ( i=1 Ei ) = i=1 µ(Ei ). The probability of a set E ∈ F is ω∈E µdω,
where the integration is made w.r.t. the measure µ.
A usual case is when Ω is the set R or all real numbers, and F is the stan-
dard Borel σ-algebra over R; that is, the smallest σ-algebra containing all open
intervals in R. In this case, µ is called a continuous probability measure, and
the integration defining the probability of a set E corresponds to the standard
Riemann integration.
If Ω is a countable (or finite) set, the standard σ-algebra is formed by the
power set of Ω, and a probability measure µPis uniquely determined by a function
µ : Ω → [0, 1]. Given a set E ⊆ Ω, µ(E) = ω∈E µ(ω); that is, the probability of
a set is the sum of the probabilities of the elements it contains. In this case, µ is
called a discrete probability measure. In addition, if µ(ω) > 0 for all ω ∈ Ω, then
µ is complete. In contrast to our definition, in a classical Kolmogorov probability
space the completeness of µ only requires it to be necessarily defined for every
ω ∈ Ω. When Ω is the set of all natural numbers N, we specify the distribution
µ as a function µ : N → [0, 1].
A simple example of a complete discrete distribution is the geometric distri-
bution. The geometric distribution Geom(p) with a parameter (the probability
of success) p ∈ (0, 1) is defined, for every i ∈ N, by µ(i) = (1 − p)i−1 p. This
distribution describes the probability of observing the first success in a repeated
trial of an experiment at time i. Returning back to the insurance example, ac-
cording to [21], an attained integer age at death has the geometrical distribution
if the force of mortality were constant at all ages.
2.2 Temporal DLs
Temporal DL-Lite logics are extensions of standard DL-Lite description logics
introduced by [1, 7]. Similarly to [3], since we want to reason about the future,
we also allow applications of the discrete unary future operators (“in the next
time point”), 2 (“always in the future”), 3 (“eventually in the future”) and the
binary operator U (“until”) to basic concepts. We use the non-strict semantics
for U, 3 and 2 in the sense that their semantics includes the current moment
of time.
Formally, TLD-Lite contains individual names a0 , a1 , . . . , concept names
A0 , A1 , . . . , flexible role names P0 , P1 , . . . and rigid role names G0 , G1 , . . . . Roles
R, basic concepts B and concepts are defined by the grammar
R ::= S | S−, S ::= Pi | Gi , B ::= ⊥ | Ai | ∃R,
C ::= B | ¬C | C | 3C | 2C | C U C | C u C.
We denote the nesting of temporal operators as the superscription of the
temporal operator from the set {2, }; that is, 20 A = 0 A = A, and 2n+1 A =
22n A, n+1 A = n
A.
A temporal concept inclusion (CI) takes the form C1 v C2 , while temporal
role inclusions (RI) are of the form R1 v R2 . As usual C1 ≡ C2 abbreviates
C1 v C2 and C2 v C1 . All CIs and RIs are assumed to hold globally (over the
whole timeline). Note that an CI can express that a basic concept is rigid, i.e.,
interpreted in the same way at every point of time. A temporal TBox T (resp.
RBox R) is a finite set of temporal CIs (resp., RIs). Their union O = T ∪ R is
called a temporal ontology. Since the non-strict operators are obviously definable
in terms of the strict ones, which do not include the current moment, tempo-
ral CIs and RIs are expressible in terms of PSpace-complete T U S DL-LiteN bool
logic [5].
A temporal interpretation is a pair I = (∆I , ·I(n) ), where ∆I 6= ∅ and
I(n) = (∆I , aI0 , . . . , AI(n)
0 , . . . , P0I(n) , . . . , GI0 , . . . , )
contains a standard DL interpretation for each time instant n ∈ N of the ordered
set (N, <), that is, aIi ∈ ∆I , AI(n)
i ⊆ ∆I and PiI(n) , GIi ⊆ ∆I × ∆I . The domain
∆ and the interpretations ai ∈ ∆I of the individual names and GIi ⊆ ∆I × ∆I
I I
of rigid role names are the same for all n ∈ N, thus, we adopt the constant
domain assumption. However, we do not assume the unique name, since neither
functionality nor number restrictions are applied to this logic.
The DL and temporal constructs are interpreted in I(n) as follows:
(R− )I(n) = {(x, y) | (y, x) ∈ RI(n) },
(∃R)I(n) = x | (x, y) ∈ RI(n) , for some y ,
(¬C)I(n) = ∆I \ C I(n) ,
I(n) I(n)
(C1 u C2 )I(n) = C1 ∩ C2 ,
[
(3C)I(n) = C I(k) ,
k≥n
\
I(n)
(2C) = C I(k) ,
k≥n
( C)I(n) = C I(n+1) ,
[ I(k) \ I(l)
(C1 U C2 )I(n) = C2 ∩ C1 .
k>l≥n
k≥n
As usual, ⊥ is interpreted by ∅ and > by ∆I for concepts and by ∆I × ∆I for
roles. As mentioned before, CIs and RIs are interpreted in I globally in the sense
that they hold in I if C1I(n) ⊆ C2I(n) and R1I(n) ⊆ R2I(n) hold for all n ∈ N.
Given an inclusion α and a temporal interpretation I, we write I |= α if α holds
in I.
2.3 Distributions of Data Instances over Time
In temporal variants of DL-Lite, instances from the ABox can be associated with
temporal constructors as well. In our logic TLD-Lite, in addition to the stan-
dard constructors used also in the ontology, we allow a probabilistic constructor
that provides a distribution of the time needed until the assertion is observed.
Formally, a TLD-Lite ABox (or data instance) is a finite set A of atoms of the
form
n n⬖ n
A(a), δ A(a), ¬A(a),
n n⬖ n
R(a, b), δ R(a, b) ¬R(a, b),
where a, b are individual names, n ∈ N and δ is a complete distribution over N.
The new constructor ⬖δ θ(a), for θ = A, a = a and θ = R, a = (a, b), expresses
that the time until the event θ(a) is first observed has distribution δ. We denote
by ind(A) the set of individual names in A. A TLD-Lite knowledge base (KB)
K is a pair (O, A), where O is a temporal ontology and A a TLD-Lite ABox.
To render the probabilistic properties, the semantics of TLD-Lite is based
on the multiple-world approach. A TLD-Lite interpretation is a pair P = (I, µ),
where I is a set of temporal interpretations I and µ is a probability distribution
over I. Given a set of temporal interpretations I, a concept name or a role θ,
individual names a and n ∈ N, let Iθa,n := {I ∈ I | aI ∈ θI(n) }. For P = (I, µ),
we interpret the probabilistic construct in I ∈ I at the time point n over the set
of individual names as
i−1
[
(⬖δ θ)I(n) = {aI | µ(Iθa,n+i \ Iθa,n+j ) = δ(i) for all i≥0}. (1)
j=0
In contrast to [14], we do not require the unique constant domain for all inter-
pretations in the set I.
P = (I, µ) is a model of K = (O, A) and write P |= K if, for any I ∈ I,
– all concept and role inclusions from O hold in I, i.e. I |= α for all α ∈ O;
– aI ∈ AI(n) for n A(a) ∈ A, and (aI , bI ) ∈ RI(n) for n R(a, b) ∈ A;
aI 6∈ AI(n) for n ¬A(a) ∈ A, and (aI , bI ) 6∈ RI(n) for n ¬R(a, b) ∈ A;
– aI ∈ (⬖δ θ)I(n) , for all n ⬖δ θ(a) ∈ A.
Similarly to the standard case, a KB K = (O, A) is consistent if it has a model.
As it is obvious from our semantics, we are using the standard open-world as-
sumption from DLs.
There are several reasons why we allow the probabilistic operator only in
ABox instances: (i) semantic: each model of K can differ in the anonymous part,
while the definition (1) requires common object names for all temporal inter-
pretations in I; (ii) computational: DL-Lite allows infinitely many anonymous
objects; bounding the probability to the ABox objects ensures existence of a
model with a finite number of terms, i.e., concept names or roles, prefixed with
⬖δ ; (iii) even leaving out the anonymous part of TLD-Lite, CIs and RIs can also
express infinitely many times repeated events for ABox objects, e.g., C v 2 C.
Remark 1. The restrictions in the syntax for avoiding uncountable models are
mainly of a technical nature: describing the distribution µ over an uncountable
set of temporal interpretations needs measure-theoretic notions; and verifying
the existence of uncountable models requires more advanced machinery.
The interpretation P = (I, µ) is countable if the set I contains countably many
temporal interpretations. In [14] it was shown that the combination 2⬖δ can
only be satisfied by an uncountable interpretation. TLD-Lite KBs allow the
constructor ⬖ only in ABox instances, and these occurrences need only a finite
number of time points to be satisfied. Hence, TLD-Lite has the countable-model
property.
Theorem 2. If a TLD-Lite KB K is satisfiable, it has a countable model.
Proof. Let P = (I, µ) be a model of K, and d be the number of all ⬖-data
instances appearing in A. If d = 0, then K does not contain any TLD-Lite in-
stances, and, for every I ∈ I, an interpretation PI = ({I}, µI ), where µI ({I}) =
1, is a model of K. Otherwise, by semantics, for every instance ni ⬖δi θi (ai ) ∈ A,
where 1 ≤ i ≤ d, we have
k−1
[
µ(Iθaii ,ni +k \ Iθaii ,ni +j ) = δi (k), (2)
j=0
for any k ≥ 0. Since the domain of probability functions, as a σ-algebra, is closed
k1 ,...,kd
under countable intersections, the joint function µ(JA,I ) is also defined for
the TLD-Lite model P = (I, µ), where
d
\ i −1
k[
k1 ,...,kd Iθi
JA,I = ai ,ni +ki \ Iθaii ,ni +j . (3)
i=1 j=0
P k1 ,...,kd
Note that {k1 ,...,kd }∈Nd µ(JA,I ) = 1.
Now from a (possibly) uncountable P we build a new countable TLD-Lite
interpretation P 0 = (I0 , ν) by assigning an appropriate weight to a representative
k1 ,...,kd
interpretation I of a set JA,I for every k1 , . . . , kd ≥ 0.
0
Initially we assume I = ∅. For all k1 , . . . , kd ≥ 0, we consider a subset
k1 ,...,kd k1 ,...,kd k1 ,...,kd
JA,I ⊆ I defined by (3). If JA,I = ∅ and µ(JA,I ) = 0, then we assign
k1 ,...,kd k1 ,...,kd
ν(JA,I 0 ) = ν(∅) = 0. Otherwise, we pick any interpretation I ∈ JA,I as
k1 ,...,kd k1 ,...,kd
a representative and set I0 = I0 ∪ I with ν(JA,I 0 ) = ν(I) = µ(JA,I ). In
the general case, the last equality, ν(I), can be equal to 0.
As d is finite and at each step of the procedure we add at most one interpre-
tation, P 0 is countable. In order to show P 0 |= K, we notice that, for any axiom
α ∈ O, we have I |= α, for any I ∈ I. Since I0 ⊆ I, we have the statement,
P 0 |= α. A similar argument can be applied to the ⬖-free ABox assertions.
Consider an instance n ⬖δ θ(a) ∈ A. By construction of P 0 = (I0 , ν), for any
k ≥ 0, it holds that
k−1
[ X k1 ,...,kd
ν({I ∈ I0 |aI ∈ θI(n+k) }\ {I ∈ I0 |aI ∈ θI(n+j) }) = ν(JA,I 0 )
j=0 {k1 ,...,kd }\{k}∈Nd−1
X k1 ,...,kd
= µ(JA,I ) = δ(k).
{k1 ,...,kd }\{k}∈Nd−1
By semantics, P 0 |= n ⬖δ θ(a). Thus, the TLD-Lite interpretation P 0 = (I0 , ν)
is a countable model of K. t
u
3 Deciding Satisfiability
We now focus on the problem of deciding whether a given TLD-Lite KB K is
satisfiable. The semantics of the ⬖-operator given by (1) in a combination with
a nondeterministic temporal operator can give interesting results.
Example 3. Consider the KB K = ({B ≡ 3A}, {⬖δ B(a)}) for a complete dis-
tribution δ. K is unsatisfiable, since, for any temporal interpretation I, the
statement I, 1 |= 3A implies I, 0 |= 3A, which contradicts the semantics of
⬖-operator (1) with i = 1, by which, for any model (I, µ) of the KB,
µ(I3A 3A
a,1 \ Ia,0 ) = δ(1) > 0.
Namely, one should not be able to say that there is any positive probability of
satisfying ¬3A(a) in a time point 0, and 3A(a) in any later time m > 0.
3.1 Multidimensional Matrix
To represent a model P = (I, µ) of a TLD-Lite KB (O, A) with d instances
of ⬖p -data assertions in the ABox, we introduce a d-dimension infinite matrix
k1 ,...,kd
MP with elements from the range of µ such that MP (k1 , . . . , kd ) = µ(JA,I ),
k1 ,...,kd
where JA,I is defined by (3). Notice that the mapping from a model to a
matrix is surjective: similarly to the proof of Theorem 2, the mapping merges
equivalent (from the point of view of ⬖ unravelling) temporal interpretations
together. Stepping away from exact TLD-Lite interpretations, by the same ar-
gument as in Theorem 2, we show the following result.
Theorem 4. A TLD-Lite KB K is satisfiable iff there is a matrix M of elements
from the interval [0, 1] such that
– for any {k1 , . . . , kd } ∈ Nd , if M (k1 , . . . , kd ) > 0 then the temporal KB
(O, Ak1 ,...,kd ), where Ak1 ,...,kd is the ⬖-free ABox
d k[
[ i −1 d
[
ni +j ni +ki ni ⬖
{ ¬θi (ai ) ∪ θi (ai )} ∪ A \ { δi θi (ai )}, (4)
i=1 j=0 i=1
is satisfiable; and
– for any 1 ≤ i ≤ d,
X
M (k1 , . . . , kd ) = δi (ki ) (5)
{k1 ,...,kd }\{ki }∈Nd−1
We consider matrix entries starting with zero; i.e., M (0, . . . , 0) is the first element
of the matrix M .
Theorem 4 allows us to avoid providing explicitly a model for a satisfiable
TLD-Lite KB, since the matrix ensures it existence. But it does not provide
an efficient solution or even an algorithm for the satisfiability problem, since it
requires an infinite matrix. However, as each non-zero element corresponds to
a classical temporal KB, we use properties of the probabilistic distribution and
establish a periodical property of matrix entries to bound the size of the matrix.
3.2 Bernoulli Processes
So far we have introduced the TLD-Lite KB in general terms. In the following
we focus on the special case where all used distributions describe a Bernoulli
process; that is, we consider only the geometric distribution, Geom(p) with 0 <
p < 1; notice that this distribution is complete. To simplify the notation, we will
simply write ⬖p for this distribution. For example, the set {⬖ 12 H(a), ⬖ 12 T (a)}
describes two experiments observing a repeated flip of the coin a, where H means
that the coin landed heads, and T ≡ ¬H that it landed tails.
The geometric distribution Geom(p) has some valuable to us properties:
1. for any j > i ≥ 0, we have Geom(p)(i) >
PGeom(p)(j); and
2. for any p > 21 and i ≥ 0, Geom(p)(i) > j>i Geom(p)(j). If p = 21 , then this
inequality becomes an equality.
We also assume that, for all ABox instances, the parameter of the geometric
distribution p is unique, 12 ≤ p < 1. To simplify presentation, particularly matrix-
wise, we consider only the case of d = 2. For an arbitrary finite d, the reasoning
we provide below is the same, but requires the use of more cumbersome notation.
We start with important properties of Geom(p) matrices for 12 ≤ p < 1.
Lemma 5. For a satisfiable TLD-Lite KB K = (O, A) with two ⬖p -instances of
Geom(p), 21 ≤ p < 1 in the ABox, and any matrix M satisfying Conditions (4)
and (5) of K, we have
1. if p > 12 , then, for any k ∈ N, the set
L(k) = {M (0, k), M (1, k), . . . , M (k, k), M (k, k − 1), . . . M (k, 0)} (6)
contains at least one non-zero element,
2. if p = 12 , then there exists at most one k ∈ N such that all elements L(k) are
zeroes.
Proof. By Property 2 of Geom and the fact that, for any matrix M of K satis-
fying (4) and (5), the elements M (k, l) and M (l, k), for all l > k, are bounded
with Geom(p)(l), the statement of item 1 is trivial.P
Item 2 follows from the fact Geom( 12 )(i) = 1
j>i Geom( 2 )(j) for all i ∈
1
P
N. Since l∈N M (k, l) = 2k+1 , if L(k) contains only zeros for some k, i.e.,
1 1
P
0≤l≤k M (k, l) = 0, then M (k, k + 1) = 2k+2 , M (k, k + 2) = 2k+3 , etc. Thus,
for all m > k the set L(m) contains at least two positive elements. t
u
The following example confirms that satisfiability of a KB depends on the chosen
parameter p.
Example 6. The TLD-Lite KB K = (O, A) with A = {⬖p H(a), ⬖p T (a)} and
O = {T ≡ ¬H} is satisfiable if p = 21 . The matrix in this case has the form
× 14 81 16
1
...
1 ×
41
M = 8 × ,
1 ×
16
... ...
where the positions × correspond to unsatisfiable temporal KBs (4), and the
matrix entries are trivially equal to 0.
However, the same TLD-Lite KB with p > 12 does not P have any model, since
M (0, 0) is unsatisfiable and the value of Geom(p)(0) > j>0 Geom(p)(j) cannot
be spread on the rest part of the matrix.
With these basic properties we can develop an (infinite) iterative process of
building a matrix for a given TLD-Lite KB K. A finite (` + 1) × (` + 1) matrix
M` is called partial, for ` ∈ N, if
– for any k1 , k2 ∈ [0, . . . , `], if M (k1 , k2 ) > 0 then the KB (O, Ak1 ,k2 ), where
Ak1 ,k2 is defined by (4), P is satisfiable; and
– for any k ∈ [0, . . . , `], 0≤{k1 ,k2 }\{k}≤` M (k1 , k2 ) = Geom(p)(k).
Clearly, if we can prove there is a partial matrix M` for all ` ∈ N, we can conclude
that TLD-Lite K is satisfiable.
Definition 7. A pair of matrix entries M (i, `), M (`, j), for i, j ≤ `, is called
chained if there is an odd chain of elements,
{M (i, `), M (i, k1 ), M (m1 , k1 ), M (m1 , k2 ), . . . , M (mh , j), M (`, j)}, (7)
where mc , kc < `, for all 1 ≤ c ≤ h ∈ N, such that, for every element of this
chain M (s, t), the temporal KB (O, As,t ) is consistent, and every even element
is in the chain, e.g., M (i, k1 ), M (m1 , k2 ), . . . , M (mh , j), is chained. Trivially,
the diagonal element M (`, `) is chained with itself, if (O, A`,` ) is consistent.
Now we are ready to prove that a pair of chained elements for every 0 ≤ k ≤ `
ensures the finite matrix M` is partial.
Lemma 8. Any TLD-Lite KB K = (O, A) with two ⬖p -instances of Geom(p),
1 n1 ⬖ n2 ⬖
2 ≤ p < 1, i.e., p θ1 (a1 ), p θ2 (a2 ) ∈ A is satisfiable iff there is a
matrix M such that either
1. for any k ∈ N, there is a chained pair in L(k); or
2. if p = 12 and there is k ∈ N with no chained elements in L(k), then a
1
submatrix Mk−1 is a partial matrix and M (i, k) = M (k, i) = 2i+1 for all
i > k.
The matrix building process is shown in the following example.
Example 9. Consider a TLD-Lite ABox {⬖p H(a), ⬖p T (a)}, where p = 21 , with
a TBox {T ≡ ¬H}. The matrix building process, according to the proof of
Lemma 8, runs as follows:
5 1 1
16 0 8 16
3 1
1
8 0 8 × 1 0 0
0
M0 = 12 , M1 = 2 1 , M2 = × 41 0 , M3 =
4
1 × × ×,...
× 4 1
× × 8
1
16 × × ×
8
The sign × denotes matrix entries of unsatisfiable temporal KBs with the cor-
responding ABoxes of the form (4), and these matrix entries are trivially equal
to 0. Iterating this process toPinfinity, the element M (0, 0), as the head of chained
pairs, stays positive as ( 21 − n≥3 21n ) = 14 . Thus, (4) and (5) hold and the TLD-
Lite KB is consistent.
It is worth noting that the condition 12 ≤ p < 1 is crucial for the building process
in Lemma 8.
Example 10. Now we let p from Example 9 be 15 . Despite the KBs for matrix
entries remaining the same, and, for all L(k), k ≥ 2, we have a pair of chained
elements, this TLD-Lite KB is unsatisfiable.
In the next subsection we demonstrate how to finitise the process in Lemma 8.
3.3 Periodical Properties
One can notice that, for a KB K, there are constants s = s(|K|) and p = p(|K|)
such that, starting from some ` > s time point, the formulas corresponding to
the elements from L(`) are equisatisfiable with some elements from L(` + p) and,
moreover, we show the following result.
Lemma 11. For any satisfiable TLD-Lite KB K over two ⬖p -data instances,
1
2 ≤ p < 1, and any matrix M satisfying (4) and (5), there exist two integers
s, p < 2O(|K|) such that, for any ` ≥ s and any pair of chained elements M (i, `)
and M (`, j), i, j ≤ `, their translations M (i0 , ` + p) and M (` + p, j 0 ) are also
chained, where
( (
0 i, if i < s, 0 j, if j < s,
i = and j = (8)
i + p, otherwise, j + p, otherwise.
Proof. The idea is based on the polynomially big (in the size of K) translation
from [4, 5] of temporal ⬖p -free KBs into equisatisfiable LTL formulas. Then, we
can use the same reasoning as for the periodic property of an LTL formula. t u
Theorem 12. Satisfiability of TLD-Lite KBs with Geom(p), 21 ≤ p < 1 can be
decided in ExpSpace.
Proof. To check if the conditions of Lemma 8(1) hold, we “guess” the positions
of unsatisfiable temporal KBs in the finite matrix Ms+p , where s + p < 2f (K)+1
and f (K) is a polynomial function. Then, for every k < s + p, among L(k) we
choose a pair of chained entries. If it is possible, Lemma 11 ensures that the
partial matrix Ms+p can be extended to infinity.
If p = 12 and there is a number k ∈ N with no chained elements in L(k) as in
Lemma 8(2), then k < s + p. Otherwise, if k ≥ s + p, it contradicts Lemma 11
which guarantees existence chained elements in L(k), if they exist for all L(i),
i < s + p. Thus, we need to find a partial matrix Mk−1 , which is in NExpSpace
as in the case 12 < p < 1, and then check the satisfiability of two exponentially
big LTL formulas with an only one ⬖p -instance. A coNExpTime oracle for
verifying this has been presented in [14].
Finally, in both cases, by Savitch’s theorem, the satisfiability problem belongs
to ExpSpace. t
u
The restriction to the geometric distribution is not essential for most results.
The main theorems
P hold for any (even not complete) distribution δ withPthe prop-
erty δ(i) > j>i δ(j), for all i, j ∈ dom(δ). However, the case δ(i) = j>i δ(j)
relies on the procedure from [14] which exploits complete distribution properties.
4 Conclusions
We have proposed a probabilistic temporal DL that is derived from a temporal
DL-Lite by specifying an exact distribution for a concept or a role in the data
to be observed. We have also provided a first but substantial analysis of the
complexity of reasoning in this logic, considering the standard reasoning task
of KB consistency. The importance of our formalism arises from the fact that
temporal observations of events can usually be predicted with a probabilistic
distribution over time; e.g., through an analysis of historical data.
This work is a first step towards a full formalism of uncertain temporal evo-
lution of events, based on DLs. Our work extends previous results [14] developed
for LTL, which can be seen as a special case of TLD-Lite where only one in-
dividual name exists. This paper provides new results, where more than one
occurrence of the distribution eventuality ⬖δ may be observed in a model.
Following the footsteps of [12], an interesting direction for future research is
to consider query answering under temporal ontologies in data-centric applica-
tions with uncertain temporal data. Along with a possible extension of temporal
ontologies with interval-valued probabilistic constraints, for future work we also
want to obtain effective methods for computing probabilities of different events
and answer different types of probabilistic queries. Another possible line for re-
search is the computation of the expected (essentially, the average) time required
until a desired property is observed, as it was previously done in [14].
References
1. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family
and relations. J. Artif. Intell. Res. (JAIR) 36, 1–69 (2009), http://dx.doi.org/
10.1613/jair.2820
2. Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., Za-
kharyaschev, M.: Ontology-mediated query answering over temporal data: A survey
(invited talk). In: 24th International Symposium on Temporal Representation and
Reasoning, TIME 2017, October 16-18, 2017, Mons, Belgium. pp. 1:1–1:37 (2017),
https://doi.org/10.4230/LIPIcs.TIME.2017.1
3. Artale, A., Kontchakov, R., Lutz, C., Wolter, F., Zakharyaschev, M.: Temporalising
tractable description logics. In: 14th International Symposium on Temporal Repre-
sentation and Reasoning (TIME 2007), 28-30 June 2007, Alicante, Spain. pp. 11–22.
IEEE Computer Society (2007), http://dx.doi.org/10.1109/TIME.2007.62
4. Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: DL-Lite with tem-
poralised concepts, rigid axioms and roles. In: Frontiers of Combining Systems,
7th International Symposium, FroCoS 2009, Trento, Italy, September 16-18, 2009.
Proceedings. pp. 133–148 (2009)
5. Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: A cookbook for
temporal conceptual data modelling with description logics. ACM Trans. Comput.
Log. 15(3), 25:1–25:50 (2014), http://doi.acm.org/10.1145/2629565
6. Billingsley, P.: Probability and Measure. John Wiley and Sons, third edn. (1995)
7. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable
reasoning and efficient query answering in description logics: The DL-Lite fam-
ily. J. Autom. Reasoning 39(3), 385–429 (2007), http://dx.doi.org/10.1007/
s10817-007-9078-x
8. Demri, S., Goranko, V., Lange, M.: Temporal Logics in Computer Science. Cam-
bridge Tracts in Theoretical Computer Science, Cambridge University Press (2016),
http://www.cambridge.org/core_title/gb/434611
9. Gabbay, D.M., Kurucz, A., Wolter, F., Zakharyaschev, M.: Many-Dimensional
Modal Logics: Theory and Applications. Elsevier North Holland (2003)
10. Gutiérrez-Basulto, V., Jung, J.C., Lutz, C., Schröder, L.: Probabilistic description
logics for subjective uncertainty. J. Artif. Intell. Res. 58, 1–66 (2017), https://
doi.org/10.1613/jair.5222
11. Halpern, J.Y.: An analysis of first-order logics of probability. Artif. Intell. 46(3),
311–350 (1990), https://doi.org/10.1016/0004-3702(90)90019-V
12. Jung, J.C., Lutz, C.: Ontology-based access to probabilistic data. In: Informal
Proceedings of the 26th International Workshop on Description Logics, Ulm, Ger-
many, July 23 - 26, 2013. pp. 258–270 (2013), http://ceur-ws.org/Vol-1014/
paper\_70.pdf
13. Klinov, P.: Practical Reasoning in Probabilistic Description Logic. Ph.D. thesis,
The University of Manchester, Manchester, UK (2011)
14. Kovtunova, A., Peñaloza, R.: Cutting diamonds: A temporal logic with proba-
bilistic distributions. In: Principles of Knowledge Representation and Reasoning:
Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona,
October 30-November 2, 2018 (2018), accepted
15. Kovtunova, A., Peñaloza, R.: Cutting diamonds: Temporal DLs with probabilistic
distributions over data. In: ArXiv e-prints. vol. 1810.01516[cs.LO] (2018), http:
//arxiv.org/abs/1810.01516
16. Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal description logics: A sur-
vey. In: Demri, S., Jensen, C.S. (eds.) 15th International Symposium on Tem-
poral Representation and Reasoning, TIME 2008, Université du Québec à Mon-
tréal, Canada, 16-18 June 2008. pp. 3–14. IEEE Computer Society (2008), http:
//dx.doi.org/10.1109/TIME.2008.14
17. Peñaloza, R., Potyka, N.: Towards statistical reasoning in description logics over
finite domains. In: Scalable Uncertainty Management - 11th International Con-
ference, SUM 2017, Granada, Spain, October 4-6, 2017, Proceedings. pp. 280–294
(2017), https://doi.org/10.1007/978-3-319-67582-4\_20
18. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under
the distribution semantics. Semantic Web 6(5), 477–501 (2015), https://doi.org/
10.3233/SW-140154
19. Sazonau, V., Sattler, U.: Tbox reasoning in the probabilistic description logic
shiqp. In: Proceedings of the 28th International Workshop on Description Log-
ics, Athens,Greece, June 7-10, 2015. (2015), http://ceur-ws.org/Vol-1350/
paper-61.pdf
20. Schmiedel, A.: Temporal terminological logic. In: Shrobe, H.E., Dietterich, T.G.,
Swartout, W.R. (eds.) Proceedings of the 8th National Conference on Artificial
Intelligence. Boston, Massachusetts, July 29 - August 3, 1990, 2 Volumes. pp. 640–
645. AAAI Press / The MIT Press (1990), http://www.aaai.org/Library/AAAI/
1990/aaai90-096.php
21. Slud, E.V.: Actuarial mathematics and life-table statistics (2006), Lecture Notes