In this paper we define an extension of a temporal description logic with a typicality operator, to allow for defeasible reasoning in a preferential temporal description logic. We show that a preferential extension of LTLℒ with typicality can be polynomially encoded into LTLℒ, and the approach allows borrowing some decidability and complexity results. We consider as well a multi-preferential temporal semantic for temporal weighted knowledge bases with typicality.
our knowledge.
To fill this gap, in this paper we develop a preferential extension of Temporal DLs, based on
the approach proposed in [
Generalizing the approach in [
We show that the preferential extension of LTLℒ with typicality can be polynomially
encoded into LTLℒ, and this approach allows borrowing decidability and complexity results
from LTLℒ. We also consider a multi-preferential extension of LTLℒ, by allowing a
conceptwise preferential semantics where different preferences are associated to different concepts. The
encoding also applies to this case. We discuss possible extensions of the closure constructions
for weighted knowledge bases [
In this section we recall the syntax and semantics of the description logic ℒ [
An ℒ interpretation is defined as a pair = ⟨Δ, · ⟩ where: Δ is a domain — a set whose elements are denoted by , , , . . . , and · is an extension function that maps each concept name ∈ to a set ⊆ Δ, each role name ∈ to a binary relation ⊆ Δ × Δ, and each individual name ∈ to an element ∈ Δ. It is extended to complex concepts: ⊤ = Δ, ⊥ = ∅, (¬) = Δ∖ , (∃.) = { ∈ Δ | ∃.(, ) ∈ and ∈ }, ( ⊓ ) = ∩ , (∀.) = { ∈ Δ | ∀.(, ) ∈ ⇒ ∈ }, ( ⊔ ) = ∪ . The notions of satisfiability of a KB in an interpretation and entailment are defined as follows: Definition 1 (Satisfiability and entailment) . Given an ℒ interpretation = ⟨Δ, · ⟩: - satisfies an inclusion ⊑ if ⊆ ; - satisfies an assertion () (resp., (, )) if ∈ (resp., ( , ) ∈ ). Given a KB = ( , ), an interpretation satisfies (resp. ) if satisfies all inclusions in (resp. all assertions in ); is a model of if satisfies and .
A concept inclusion = ⊑ (resp., an assertion (), (, )), is entailed by , written |= , if for all models =⟨Δ, · ⟩ of , satisfies .
Given a knowledge base , the subsumption problem is the problem of deciding whether an inclusion ⊑ is entailed by . The satisfiability problem is the problem of deciding whether a knowlwdge base has a model. The concept satisfiability problem is the problem of deciding, for a concept , whether is consistent with (i.e., whether there exists a model of , such that ̸= ∅).
The concepts of the temporal description logic LTLℒ can be formed from standard constructors using the temporal operators ○ (next), (until), ◇ (eventually) and □ (always) of linear time temporal logic (LTL). The set of temporally extended concepts is as follows:
::= | ⊤ | ⊥ | ⊓ | ⊔ | ¬ | ∀. | ∃. | ○ | | ◇ | □ where ∈ , and and are temporally extended concepts.
A temporal interpretation for LTLℒ is a pair ℐ = (Δℐ , · ℐ ), where Δℐ is a nonempty
domain; · ℐ is an extension function that maps each concept name ∈ to a set ℐ ⊆ N × Δℐ ,
each role name ∈ to a relation ℐ ⊆ N × Δℐ × Δℐ , and each individual name ∈ to
an element ℐ ∈ Δℐ . Following [
Δℐ )∖ℐ ( ⊔ )ℐ = ℐ ∪ ℐ Δℐ | ∃.(, , ) ∈ ℐ and (, ) ∈ ℐ } Δℐ | ∀.(, , ) ∈ ℐ ⇒ (, ) ∈ ℐ } Δℐ | ( + 1, ) ∈ ℐ } Δℐ | ∃ ≥ such that (, ) ∈ ℐ } Δℐ | ∀ ≥ , (, ) ∈ ℐ } ( )ℐ = {(, ) ∈ N × Δℐ | ∃ ≥ s.t. (, ) ∈ ℐ
and (, ) ∈ ℐ , ∀ ( ≤ < )} While the definition above assumes a constant domain (i.e., that the domain elements are the same at all time points), in the following we will also consider the case with expanding domains, when there is a sequence of increasing domains Δ0ℐ ⊆ Δ1ℐ ⊆ . . ., one for each time point.
Let a TBox be a set of concept inclusions ⊑ , where , are temporally extended
concepts, as above. It has been proven that concept satisfiability in LTLℒ w.r.t. TBoxes is
EXPTIME-complete, both with expanding domains [
The complexity of other cases and, specifically, the cases of temporal ABoxes [
In the next section we develop a preferential extension of LTLℒ. For simplicity, we focus on the case of non-temporal ABox and TBox, i.e., with the TBox containing a set of concept inclusions ⊑ , where , are temporally extended concepts, but without temporal operator applied to the concept inclusions themselves. 4. LTLT ℒ
: A Preferential Extension of LTLℒ with Typicality
In this section we define an extension of the temporal description logic LTLℒ allowing
typicality concepts of the form T(), where is a LTLℒ concept. The instances of T() are
intended to be the typical instances of a concept . Following [
Unlike [
T(Professor ) ⊑ (∃teaches.Course) Semester _End ∃lives_in.Town ⊓ Young ⊑ T(◇∃granted .Loan) The first inclusion means that normally professors teach at least a course until the end of the semester (but exceptions are allowed). The second one means that persons living in town and being young are typical in the set of individuals eventually being granted a loan. theWloegdicefineℒapr[e5f]e,rwenetdiaelfineexttheenssieomna,ntLicTsLoTfℒL,ToLfTLℒTLinℒt er.mAssoffoprrtehfeerpernetfiearlemnotidaellesx,teexntseinodninogf ordinary models of LTLTℒ with a preference relation < on the domain, whose intuitive meaning is to compare the “typicality” of domain elements, that is to say, < means that domain element is more typical than . The typical instances of an (extended) concept (the instances of T()) are the instances of that are minimal with respect to the preference relation < (i.e., no other instances of are preferred to ).
In the following, we will consider a collection of preference relations <, one for each time point . They will be defined as the projections of a relation < over the single time points. Definition 2 (Preferential temporal interpretations for LTLT ℒ structure ℳ = (Δℐ , <, · ℐ ) where: ). An LTLT ℒ interpretation is a • (Δℐ , · ℐ ) is a temporal interpretation as for LTLℒ , as introduced in Section 3, but the interpretation function · ℐ is extended to typicality concepts (see below); • the relation < ⊆ N × Δℐ × Δℐ associates to each time point a preference < over the domain Δℐ such that, for all ∈ N, < = {(, ) | (, , ) ∈ <} and relation < is an irreflexive, transitive and well-founded relation over Δℐ ; • the interpretation of typicality concepts T() is defined as follows:
(T())ℐ = {(, ) | ∈ Min < (ℐ ), for ∈ N} where ℐ = { | (, ) ∈ ℐ } are the instances of at time point , and Min < () = { : ∈ and ∄ ∈ s.t. < }.
Furthermore, we say that relation < is well-founded if, for all ⊆ ∈ Min < () or ∃ ∈ Min < () such that < . Δℐ , for all ∈ , either
For each timepoint , relation < has the properties of preference relation in KLM preferential
interpretations [
The relation < can be regarded as a function associating to each time point a preference relation < over Δℐ , i.e., < ⊆ Δℐ × Δℐ . At each time point , the typicality concept T() is interpreted as the set of maximally preferred -elements, according to the preference relation < for time point .
As for the temporal language LTLℒ [
The notions of satisfiability and model of a knowledge base can be easily extended to LTLT ℒ with non-temporal ABox and TBox. As is a non-temporal ABox, the assertions in are evaluated at time point 0. On the other hand, all inclusions in the (non-temporal) TBox have to be satisfied at all time points.
Definition 3 (Satisfiability in LTLTℒ ). Given an LTLTℒ interpretation ℳ = ⟨Δℐ , <, · ℐ ⟩, ℳ satisfies a concept inclusion ⊑ iff ℐ ⊆ ℐ ; ℳ satisfies an assertion () (resp., (, )) iff (0, ℐ ) ∈ ℐ (resp., (0, ℐ , ℐ ) ∈ ℐ ).
Given an LTLTℒ knowledge base = ( , ), the interpretation ℳ is a model of if ℳ satisfies all concept inclusions in and all assertions in . An LTLTℒ knowledge base = ( , ) is satisfiable in LTLTℒ if a model ℳ = ⟨Δℐ , <, · ℐ ⟩ of exists.
The fact that each irreflexive and transitive relation < on Δ is well-founded guarantees that, for any <, there are no infinite descending chains of elements of Δℐ .
At any time point there is a possibly different relation <, which allows to identify the
typical instances of a concept at any time point . As observed in [
This modal interpretation of the typicality operator T in terms of a Gödel-Löb modality □<
has been used to define an encoding of ℛℐ T into ℛℐ [
ℒ In this section we show that reasoning in LTLTℒ can be reduced polynomially to reasoning in LTLℒ . The idea, as reported above, is to define an encoding of the typicality concept in the temporal description logic, by interpreting T() as a formula ⊓ □<¬, where the accessibility relation of the modality □< is the inverse of the preference relation.
The interpretation of T() at a time point is to be evaluated based on the preference relation < at time point , i.e., based on <. We represent the preference relation < in a preferential temporal interpretation ℳ (see Definition 2) by introducing a new role < in the language. Also, we represent a concept T() with the concept ⊓ □¬ , where □¬ is a new concept name which is intended to capture the meaning of formula □<¬ (dropping the < to make notation lighter). Finally, we will introduce additional concept inclusion axioms to capture the interplay between role < and the new concepts □¬ , as well as to enforce the properties of the preference relations <.
Let = ( , ) be a LTLTℒ knowledge base and let , , be the set of concept names, role names and individual names in the language of . We define the encoding ′ = ( ′, ′) of in LTLℒ over the concept names, role names and individual names in ′ , ′, ′ , as follows.
The language of ′ contains all the individual names, concept names and role names in the language of (i.e., ⊆ ′ , ⊆ ′, ⊆ ′ ). For each T() occurring in (where is any, possibly complex, temporally extended concept), we introduce in ′ a new atomic concept □¬ and, for each inclusion ⊑ ∈ , we introduce in ′ the inclusion ′ ⊑ ′, where ′ and ′ are obtained from and , respectively, by replacing the occurrence of any concept T() with the concept ⊓ □¬. Note that concept □¬ may have a different interpretation at each time point.
As mentioned above, to capture the properties of the □< modality, a new role name < is
introduced to represent the relation < in preferential models, and the following concept inclusion
axioms are introduced in ′, for all concepts such that T() occurs in :
□¬ ⊑ ∀<.(¬ ⊓ □¬)
¬□¬ ⊑ ∃<.( ⊓ □¬)
(1)
(2)
The first inclusion accounts for the transitivity of the preference relations <. The second
inclusion accounts for the smoothness (see [
We also define ABox ′ by replacing each occurrence of the concept T() in any individual assertions () in , with the concept ⊓□¬, and by including in ′ all the resulting assertions. All the assertions of the form (, ) ∈ are included unaltered in ′.
Proposition 1. For a temporal knowledge base = ( , ) in LTLT ℒ, let ′ be the encoding of in LTLℒ. It holds that is satisfiable in LTLTℒ iff ′ is satisfiable in LTLℒ.
As it is clear, the encoding above is polynomial in the size of the knowledge base and, more precisely, if || is the size of , the size of ′ is (||).
As a consequence of Proposition 1, the decidability and complexity results that have been proven to hold for the temporal description logic LTLℒ also extend to the preferential temporal description logic LTLTℒ. Note that our encoding does not depend on assumptions on constant domains, and it works as well for expanding domains.
In particular, for non-temporal TBoxes , that is, a set of concept inclusions ⊑ , where
, are LTLTℒ concepts, the following holds as a consequence of the encoding above and of
the results for LTLℒ with expanding domains and with constant domains [
ℒ expanding domains and with constant domains.
w.r.t. TBoxes is EXPTIME-complete, both with
Note that this encoding which exploits ℒ constructs can as well be adopted for more expressive logics, although for expressive DLs alternative encodings might be viable. The preferential extension LTLT
ℒ and its encoding in LTLℒ can as well be considered for knowledge bases with temporal TBoxes and temporal ABoxes, with minor modifications of the proof of Proposition 1. While we leave the detailed treatment of these cases for future work, in the next sections, we move to consider a multi-preferential semantics for temporal ℒ with typicality, as well as possible closure constructions for these extension.
Following [
ℒ concept in a set of distinguished concepts = {1, . . . , }. The underlying idea is that the distinguished concepts represent the aspects with respect to which domain individuals are compared. For instance, Tom may be more typical than Bob as a student (tom <S bob), but less typical as an employed student (bob <ES tom).
In the temporal case, this means that, at each time point , there are different preference relations <1 , . . . , < one for each ∈ . Let us assume, for the moment, that the typicality operator only applies to the distinguished concepts . The notion of multi-preferential temporal interpretation for T, is defined as follows:
ℒ (Δℐ , <1 , . . . , < , · ℐ ) where: Definition 4 (Multi-preferential temporal interpretations for T, ). Let = {1, . . . , } ℒ be a set of distinguished concepts. An T, interpretation over is a structure ℳ = ℒ • Δℐ is a nonempty domain; • for each ∈ , relation < ⊆ N × Δℐ × Δℐ associates to each time point a preference < over the domain Δℐ such that, for all ∈ N, < = {(, ) | (, , ) ∈< } and relation < is an irreflexive, transitive and well-founded relation over Δℐ ; • The interpretation function · ℐ , introduced in Section 3 for temporally extended goals, is extended to typicality concepts T() as follows:
(T())ℐ = {(, ) | ∈ Min< (ℐ,), for ∈ N} where ℐ, = { | (, ) ∈ ℐ } are the instances of at time point .
Let us define an Tℒ, knowledge base = ⟨ , ⟩ as an LTLTℒ knowledge base in which only typicality concepts of the form T() may occur. An encoding in LTLℒ of the different preference relations associated to concepts can be defined in a similar way as for the single preference relation <, but requires to introduce a new role < , for each distinguished concept ∈ , as well as a new concept name □¬ to encode a typicality concept T() occurring in the TBox with concept ⊓ □¬ in LTLℒ . The two axioms, (1) and (2) need as well to be introduced for all ∈ .
The result that concept satisfiability in LTLTℒ w.r.t. TBoxes is EXPTIME-complete also
extends to the multi-preferential temporal ℒ under the T, semantics.
ℒ
6.1. Global Preference
Note that, given the preferences < for the distinguished concepts, one can interpret T() at
time point as the set of minimal elements w.r.t. < . However, to provide an interpretation of
the typicality concept T() for an arbitrary (such as, for instance, T(Employee ⊓ Student )),
one would need to define a preference relation with respect to or, in alternative, a notion
of global preference relation. Many notions of preference combination have been considered
and studied in the literature [
() for all ∈ , ≤ or ∃ℎ(ℎ ≻ and <ℎ ).
We interpret T(), for an arbitrary concept , at time point , as the set of minimal -elements with respect to <, i.e., (T())ℐ = {(, ) | ∈ Min< (ℐ ), for ∈ N}, where ℐ = { | (, ) ∈ ℐ } are the instances of concept at time point . This leads to the definition of a concept-wise multi-preferential temporal interpretation (cw-interpretation) for T, as a a tuple ℳ = ⟨Δ, <1 , . . . , < , <, · ⟩, where ⟨Δ, <1 , . . . , < , · ⟩ is an T,ℒ preferential temporal interpretation (see Definition 4), and <⊆ N × Δ × Δ is a globalpℒrefemreunlctierelation, defined from the relations <⊆ Δℐ × Δℐ as follows: (, , ) ∈< iff (, ) ∈<.
classes, while Bob is not young, has a boss and has no classes, considering the weights above, we will regard Bob as being more typical than Tom as an employee at .
Given a temporal interpretation ℐ = (Δℐ , · ℐ ) for LTLℒ , we say that ∈ Δℐ satisfies T() ⊑ in ℐ at time point , if (, ) ̸∈ ℐ or (, ) ∈ ℐ (otherwise violates T() ⊑ in ℐ at time point ). For a concept ∈ and a domain element ∈ Δℐ , the weight ℐ,() of w.r.t. in ℐ at time point , is defined considering the inclusions (T() ⊑ ℎ , ℎ ) ∈ , as follows: ℐ,() = {︃ ∑︀ −∞ ℎ:(,)∈ℎℐ ℎ if ∈ ℐ, otherwise where −∞ is added at the bottom of real values. Informally, given an interpretation ℐ, for (, ) ∈ ℐ , the weight ℐ,() of wrt at time point is the sum of the weights of all defeasible inclusions for satisfied by in ℐ at time point . The more plausible are the satisfied inclusions, the higher is the weight of . The lowest weight, −∞ , is given to all domain elements which are not instances of at time point .
Based on this notion of weight of a domain element wrt a concept, a preference relation < can be built from a given interpretation ℐ and a weighted knowledge base . At time point , an element is preferred to element wrt if the sum of the weights of the defaults in satisfied by at is higher than the sum of the weights of defaults in satisfied by at : for , ∈ Δ, < iff ℐ,() > ℐ,() (3) (4) Note that < is a strict modular and well-founded partial order, and all -elements are preferred wrt < to the domain elements which are not instances of . The higher is the weight of an element wrt (at ) the more preferred is the element w.r.t. at time point . In the example above, ℐ,() = 30 > ℐ,() = − 70 (for = Emp) and, hence, bob <Emp tom , i.e., Bob is more typical than Tom as an employee.
Let us define a concept-wise multi-preferential temporal semantics (cw temporal semantics) for a weighted knowledge base.
Definition 5. A concept-wise multi-preferential temporal model (cw-model) of a weighted T, knowledge base = ⟨ , 1 , . . . , , ⟩ over is a concept-wise multi-preferential ℒ interpretation ℳ = ⟨Δℐ , <1 , . . . , < , <, · ℐ ⟩, such that: for all = 1, . . . , , < = {(, , ) : ∈ N and < }, where each < is defined from and ⟨Δℐ , · ℐ ⟩, according to condition (4); < is the resulting global preference relation, as defined in Section 6.1; and ⟨Δℐ , <, · ℐ ⟩ satisfies and according to satisfiability in Definition 3.
Based on the notion of cw-model of a KB, the notions of concept-wise entailment (or
cwentailment) and canonical cw-entailment can be defined in a natural way for weigthed KBs in
T, , as in the non-temporal case [
ℒ
Let us restrict consideration to canonical models, i.e., models which are large enough to
contain all the relevant domain elements (see [
Definition 6. Given a ranked knowledge base = ⟨ , 1 , . . . , , ⟩ a model ℳ = ⟨Δℐ , <1 , . . . , < , <, · ℐ ⟩ of is canonical for if, for any set of concepts {1, . . . , } ⊆ Conc such that 1 ⊓ . . . ⊓ is satisfiable with respect to ⟨ , ⟩, it holds that for all time points , there exists a domain element ∈ Δℐ such that (, ) ∈ ℐ for all = 1, . . . , .
The idea is that, in a canonical model for , any conjunction of concepts occurring in , or
their complements, when consistent with the TBox and the ABox of , must have some
instance in the domain at each time point . Existence of canonical interpretations has been
proven in the non-temporal case for knowledge bases which are consistent under the preferential
(or ranked) semantics for typicality [
Definition 7 (cw-entailment [
The study of the properties of this semantic, such as the KLM properties [
In this paper we have developed a preferential temporal description logics with typicality LTLTℒ. The monotonic logic LTLT
ℒ can be further extended to define a semantics for weighted
knowledge bases, by introducing multiple preferences. The paper discusses these extensions,
showing that the concept-wise multi-preferential semantic in [
On a different route, a preferential LTL with defeasible temporal operators has been studied in
[
A different approach for combining defeasibility in temporal DL formalism has been proposed
in [
into LTLℒ provides decidability and complexity results for the for free. For the multi-preferential case, proof methods for defeasible temporal reasoning with weighted knowledge bases have to be investigated, possibly for fragments of T, . This will be subject of future work.
ℒ
We thank the anonymous referees for their helpful comments. This work was partially supported by GNCS-INdAM. Mario Alviano was partially supported by Italian Ministry of Research (MUR) under PNRR project FAIR “Future AI Research”, CUP H23C22000860006, under PNRR project Tech4You “Technologies for climate change adaptation and quality of life improvement”, CUP H23C22000370006, and under PNRR project SERICS “SEcurity and RIghts in the CyberSpace”, CUP H73C22000880001; by Italian Ministry of Health (MSAL) under POS project RADIOAMICA, CUP H53C22000650006; by the LAIA lab (part of the SILA labs). answer sets, Theory and Practice of Logic Programming 13 (2013) 201–225. [29] J. Henriksen, P. Thiagarajan, Dynamic Linear Time Temporal Logic, Annals of Pure and
Applied logic 96 (1999) 187–207. [30] L. Giordano, A. Martelli, D. Theseider Dupré, Achieving completeness in the verification of action theories by bounded model checking in ASP, J. Log. Comp. 25 (2015) 1307–30. [31] F. Baader, C. Lutz, M. Milicic, U. Sattler, F. Wolter, Integrating description logics and action formalisms: First results, in: Proc. AAAI 2005, 2005, pp. 572–577. [32] H. Liu, C. Lutz, M. Milicic, F. Wolter, Reasoning about actions using description logics with general tboxes, in: Proc. JELIA 2006, Liverpool, UK, 2006, pp. 266–279. [33] F. Baader, M. Lippmann, H. Liu, Using causal relationships to deal with the ramification problem in action formalisms based on description logics, in: LPAR-17, 2010, pp. 82–96.