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