Recent work has studied a probabilistic extension of the temporal 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 extension 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.
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) uncertainty.
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 probabilities 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 probability for an individual in the domain to be randomly picked, we choose the subjective view, which specifies the probability distribution over a set of possible 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 knowledge, 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 property 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 proposed in [5] with temporal data specified by the geometric distribution with parameter p 21 .
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 properly 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, introduce 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
We briefly introduce the basics of probability theory and temporal extensions of description logics. 2.1
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 any countable collection of pairwise disjoint sets Ei 2 F , i 1, it holds that (Si1=1 Ei) = Pi1=1 (Ei): The probability of a set E 2 F is R!2E 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 standard 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 is uniquely determined by a function : ! [0; 1]. Given a set E , (E) = P!2E (!); 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 ! 2 , 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 ! 2 . 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 distribution. The geometric distribution Geom(p) with a parameter (the probability of success) p 2 (0; 1) is defined, for every i 2 N, by (i) = (1 p)i 1p. 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, according 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 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 j C ::=
S ;
S ::= B j :C j
Pi j Gi; C j 3C
B ::= j 2C j ? j C U C
Ai j 9R; j
C u C:
We denote the nesting of temporal operators as the superscription of the temporal operator from the set f2; g; that is, 20A = 0A = A, and 2n+1A = 22nA, n+1A = nA.
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, temporal CIs and RIs are expressible in terms of PSpace-complete T US DL-LitebNool logic [5].
A temporal interpretation is a pair I = ( I ; I(n)), where I 6= ; and
I(n) = ( I ; a0I ; : : : ; A0I(n); : : : ; P0I(n); : : : ; G0I ; : : : ; ) contains a standard DL interpretation for each time instant n 2 N of the ordered set (N; <), that is, aiI 2 I , AiI(n) I and PiI(n); GiI I I . The domain
I and the interpretations aiI 2 I of the individual names and GiI I I of rigid role names are the same for all n 2 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) = f(x; y) j (y; x) 2 RI(n)g; (9R)I(n) = x j (x; y) 2 RI(n); for some y ; (:C)I(n) =
I n CI(n); (C1 u C2)I(n) = C1I(n) \ C2I(n); (3C)I(n) = [ CI(k); (2C)I(n) = \
k n ( C)I(n) = CI(n+1);
CI(k); k n k n (C1 U C2)I(n) = [
CI(k) 2 \ \ k>l n
CI(l) : 1 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 2 N. Given an inclusion and a temporal interpretation I, we write I j= if holds in I. 2.3
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 standard 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
nA(a); nR(a; b);
nÑ A(a); nÑ R(a; b)
n:A(a); n:R(a; b); where a, b are individual names, n 2 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 2 N, let Ia;n := fI 2 I j aI 2 I(n)g. For P = (I; ), we interpret the probabilistic construct in I 2 I at the time point n over the set of individual names as (Ñ
i 1
)I(n) = faI j (Ia;n+in [ Ia;n+j ) = (i) for all i 0g:
j=0
(
P = (I; ) is a model of K = (O; A) and write P j= K if, for any I 2 I, – all concept and role inclusions from O hold in I, i.e. I j= for all – aI 2 AI(n) for nA(a) 2 A, and (aI ; bI ) 2 RI(n) for nR(a; b) 2 A; aI 62 AI(n) for n:A(a) 2 A, and (aI ; bI ) 62 RI(n) for n:R(a; b) 2 A; – aI 2 (Ñ )I(n), for all nÑ (a) 2 A. 2 O; 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 assumption 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 (
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 instances, and, for every I 2 I, an interpretation PI = (fIg; I ), where I (fIg) = 1, is a model of K. Otherwise, by semantics, for every instance ni Ñ i i(ai) 2 A, where 1 i d, we have (Iaii;ni+k n k 1 [ Iaii;ni+j ) = i(k); j=0 d 0 k1;:::;kd = \ JA;I i=1
Iaii;ni+j A : ki 1 [ j=0 1 for any k 0. Since the domain of probability functions, as a -algebra, is closed under countable intersections, the joint function (JAk1;I;:::;kd ) is also defined for the TLD-Lite model P = (I; ), where Note that Pfk1;:::;kdg2Nd (JAk1;I;:::;kd ) = 1.
Now from a (possibly) uncountable P we build a new countable TLD-Lite interpretation P0 = (I0; ) by assigning an appropriate weight to a representative interpretation I of a set JAk1;I;:::;kd for every k1; : : : ; kd 0.
Initially we assume I0 = ;. For all k1; : : : ; kd 0, we consider a subset
JAk1;I;:::;kd I defined by (
As d is finite and at each step of the procedure we add at most one interpre0 = K, we notice that, for any axiom tation, P0 is countable. In order to show P j
2 O, we have I j= , for any I 2 I. Since I0 I, we have the statement, P0 j= . A similar argument can be applied to the Ñ-free ABox assertions.
Consider an instance nÑ (a) 2 A. By construction of P0 = (I0; ), for any
k 0, it holds that
(
I(n+k) gn k 1 [ fI 2 I0jaI 2 j=0
I(n+j)g) = X
(JAk1;I;:0::;kd ) fk1;:::;kdgnfkg2Nd 1
= X By semantics, P0 j= nÑ is a countable model of K. 3
(a). Thus, the TLD-Lite interpretation P0 = (I0; )
We now focus on the problem of deciding whether a given TLD-Lite KB K is
satisfiable. The semantics of the Ñ-operator given by (
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
MP with elements from the range of such that MP (k1; : : : ; kd) = (JAk1;I;:::;kd ),
k1;:::;kd is defined by (
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 fk1; : : : ; kdg 2 Nd, if M (k1; : : : ; kd) > 0 then the temporal KB (O; Ak1;:::;kd ), where Ak1;:::;kd is the Ñ-free ABox d ki 1 [ [
f i=1 j=0 is satisfiable; and – for any 1 i d, ni+j : i(ai) [
d ni+ki i(ai)g [ A n f [ i=1
ni Ñ i i(ai)g;
X fk1;:::;kdgnfkig2Nd 1
M (k1; : : : ; kd) = i(ki)
tu
(
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
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 sdiemscprliybewsrtiwteoÑexppfoerrimtheisntdsisotbrsiberuvtiinogn.aFroerpeeaxtaemdpflliep, tohfethseetcofiÑn 21aH,w(ah)e;re ÑH12mTe(aan)gs 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) > Geom(p)(j); and 2. for any p > 12 and i 0, Geom(p)(i) > Pj>i Geom(p)(j). If p = 12 , 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 matrixwise, 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 21 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 (
L(k) = fM (0; k); M (1; k); : : : ; M (k; k); M (k; k
1); : : : M (k; 0)g
(
Proof. By Property 2 of Geom and the fact that, for any matrix M of K
satisfying (
Item 2 follows from the fact Geom( 21 )(i) = Pj>i Geom(
Example 6. The TLD-Lite KB K = (O; A) with A = fÑpH(a); ÑpT (a)g and
O = fT :Hg is satisfiable if p = 12 . The matrix in this case has the form
where the positions correspond to unsatisfiable temporal KBs (
However, the same TLD-Lite KB with p > 12 does not have any model, since M (0; 0) is unsatisfiable and the value of Geom(p)(0) > Pj>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 ` 2 N, if – for any k1; k2 2 [0; : : : ; `], if M (k1; k2) > 0 then the KB (O; Ak1;k2 ), where
Ak1;k2 is defined by (
Definition 7. A pair of matrix entries M (i; `); M (`; j), for i; j
chained if there is an odd chain of elements,
`, is called
fM (i; `); M (i; k1); M (m1; k1); M (m1; k2); : : : ; M (mh; j); M (`; j)g;
(
Now we are ready to prove that a pair of chained elements for every 0 ensures the finite matrix M` is partial. k ` Lemma 8. Any TLD-Lite KB K = (O; A) with two Ñp-instances of Geom(p), 12 p < 1, i.e., n1 Ñp 1(a1); n2 Ñp 2(a2) 2 A is satisfiable iff there is a matrix M such that either 1. for any k 2 N, there is a chained pair in L(k); or 2. if p = 21 and there is k 2 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 fÑpH(a); ÑpT (a)g, where p = 12 , with a TBox fT :Hg. The matrix building process, according to the proof of Lemma 8, runs as follows:
M0 =
The sign denotes matrix entries of unsatisfiable temporal KBs with the
corresponding ABoxes of the form (
It is worth noting that the condition 12 in Lemma 8. p < 1 is crucial for the building process 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
One can notice that, for a KB K, there are constants s = s(jKj) and p = p(jKj) 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,
12 p < 1, and any matrix M satisfying (
(
If p = 12 and there is a number k 2 N with no chained elements in L(k) as in
Lemma 8(
Finally, in both cases, by Savitch’s theorem, the satisfiability problem belongs to ExpSpace. tu
The restriction to the geometric distribution is not essential for most results. The main theorems hold for any (even not complete) distribution with the property (i) > Pj>i (j), for all i; j 2 dom( ). However, the case (i) = Pj>i (j) relies on the procedure from [14] which exploits complete distribution properties. 4
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 evolution 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 individual 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
applications 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
research is the computation of the expected (essentially, the average) time required
until a desired property is observed, as it was previously done in [14].
16. Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal description logics: A
survey. In: Demri, S., Jensen, C.S. (eds.) 15th International Symposium on
Temporal Representation and Reasoning, TIME 2008, Université du Québec à
Montré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
Conference, 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(