Preferential Temporal Description Logics with Typicality and Weighted Knowledge Bases (Extended Abstract)

Abstract

In this extended abstract we report about an extension of a temporal description logic with a typicality operator, to allow for defeasible reasoning in a preferential temporal description logic. The preferential temporal logic with typicality LTLTℒ can be polynomially encoded into LTLℒ, and the approach allows borrowing decidability and complexity results from LTLℒ. This extended abstract reports about our work which aims at combining some temporal extension of Description Logics (DLs) based on LTL and preferential DLs with typicality. LTL extensions of Description Logics are very well-studied in DLs literature, and we refer to [1, 2] for surveys on temporal DLs and their complexity and decidability. Preferential extensions of DLs allow reasoning with exceptions through the identification of prototypical properties of individuals or classes of individuals. Defeasible inclusions are allowed in the knowledge base, to model typical, defeasible, non-strict properties of individuals. Their semantics extends DLs semantics with a preference relation among domain individuals, along the lines of the preferential semantics introduced by Kraus, Lehmann and Magidor [3, 4] (KLM for short). In the literature, several preferential extensions and rational extensions of the description logic ℒ [5] have been studied [6, 7], and different closure constructions have been developed [8, 9, 10, 11, 12, 13], inspired by Lehmann and Magidor's rational closure [4] and Lehmann's lexicographic closure [14]. More recently, multi-preferential extensions of DLs have also been developed, by allowing multiple preference relations with respect to different concepts [15, 13, 16, 17], and to provide semantics for ranked and for weighted knowledge bases with typicality.

1. Introduction

While preferential extensions of propositional LTL with defeasible temporal operators have been recently studied [ 18, 19, 20 ] to enrich temporal formalisms with non-monotonic reasoning features, preferential extensions (and, more specifically, typicality based extensions) of temporal DLs have not been considered so far, up to our knowledge.

To fill this gap, in this work we develop a preferential extension of Temporal DLs, based on the approach proposed in [ 7 ] to define a description logic with typicality. Generalizing the approach to the temporal case, we define a preferential temporal description logic with typicality, LTLTℒ , by adding to the language of LTLℒ a typicality operator T that selects the most typical instances of a concept . The resulting temporal DL with typicality allows for representing temporal properties of concepts which admit exceptions, e.g., that normally professors teach at least a course until they retire, but exceptions are permitted.

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ℒ , and discuss a possible extension of the closure constructions for weighted knowledge bases [ 16, 21 ] to the temporal case. An extended version of this work has been presented in [22].

2. Temporal Description Logic LTL

ℒ 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 [ 1 ] we assume individual names to be rigid, i.e., having the same interpretation at any time point. In a pair (, ) ∈ N × ∆ ℐ , represents a time point and a domain element; (, ) ∈ ℐ means that is an instance of concept at time point , and similarly for (, 1, 2) ∈ ℐ . Function · ℐ is extended to complex concepts as follows: ⊤ℐ = N × ∆ ℐ ⊥ℐ = ∅ (¬)ℐ = (N × ∆ ℐ )∖ℐ (∃.)ℐ = {(, ) ∈ N × ∆ ℐ | ∃.(, , ) ∈ ℐ and (, ) ∈ ℐ } ( ⊓ )ℐ = ℐ ∩ ℐ (○ )ℐ = {(, ) ∈ N × ∆ ℐ | ( + 1, ) ∈ ℐ } ( )ℐ = {(, ) ∈ N × ∆ ℐ | ∃ ≥ s.t. (, ) ∈ ℐ

and (, ) ∈ ℐ , ∀ ( ≤ < )} The operators ⊔, ∀, □ and ◇ can be defined from the others, as usual. 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.

For simplicity, we will focus on the case of non-temporal ABox and TBox. 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 [23] and with constant domains [ 1 ].

3. A Preferential Extension of LTL

ℒ with Typicality We define an extension of the temporal description logic LTLℒ allowing typicality concepts of the form T(), where is an LTLℒ concept. The instances of T() are intended to be the typical instances of a concept . Following [ 7 ], we call T a typicality operator.

When concept T() is used on the left hand side of concept inclusions, defeasible properties of a concept of the form T() ⊑ can be expressed, meaning that the typical instances of concept are also instances of concept (normally, ’s are ’s). We can therefore distinguish between properties that hold for all instances of , expressed by strict inclusions ( ⊑ ), and those that only hold for the typical instances of , expressed by typicality or defeasible inclusions (T() ⊑ ). However, in agreement with [24, 25], we do not require that the typicality operator only occurs on the left hand side of concept inclusions. As usual, the typicality operator T cannot be nested. Extended concepts can be built by adding the typicality operator to the concept constructors of LTLℒ . They can freely occur in concept inclusions, such as, for instance, in: T(Professor ) ⊑ (∃teaches .Course) Retired ∃lives _in.Town ⊓ Young ⊑ T(◇∃granted .Loan) where the first inclusion means that normally professors teach at least a course until he retires (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. An ABox may, e.g., contain the assertions: Professor (john), ◇Retired (john), lives _in(ℎ, ℎ), Town (athens ).

As for the preferential extension of the logic ℒ [ 7 ], we define the semantics of LTLTℒ in terms of preferential models, extending ordinary LTLTℒ models with a preference relation < on the domain, intended to compare the “typicality” of domain elements: < means that domain element is more typical than . 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 1 (Preferential temporal interpretations for LTLTℒ ). An LTLTℒ interpretation is a structure ℳ = (∆ ℐ , <, · ℐ ) where: (i) (∆ ℐ , · ℐ ) is a temporal interpretation as for LTLℒ , as introduced in Section 2, but the interpretation function · ℐ is extended to typicality concepts (see below); (ii) 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 ∆ ℐ ; (iii) the interpretation of typicality concepts T() is defined as (T())ℐ = {(, ) | ∈ Min < (ℐ ), for ∈ N}, where ℐ = { | (, ) ∈ ℐ } are the instances of at time point , and Min < () = { : ∈ and ∄ ∈ s.t. < }.

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 2 (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 < to identify the typical instances of a concept at time point .

As observed in [ 7 ] for ℒ with typicality, the meaning of T can be split into two parts: for any element ∈ ∆ ℐ , ∈ (T())ℐ when (i) ∈ ℐ , and (ii) there is no ∈ ℐ such that < (note that, for ℒ with typicality, there is a single preference relation < on the domain ∆ ℐ ). Following [ 7 ], in order to isolate the second part of the meaning of T, one can introduce a Gödel-Löb modality (for which we use the symbol □<), and interpret the preference relation < as the inverse of the accessibility relation of this modality at time point . Well-foundedness of < ensures that typical elements of ℐ exist whenever ℐ ̸= ∅, by avoiding infinitely descending chains of elements. As for the case of ℒ with typicality in [ 7 ], it can be proven that is a typical instance of at time point if and only if it is an instance of and □<¬.

An encoding of an LTLTℒ knowledge base into LTLℒ can be defined by introducing: a new role < in the DL language to represent the preference relation; for each T() occurring in , a new named concept □¬, and two inclusion axioms, □¬ ⊑ ∀<.(¬ ⊓ □¬) and ¬□¬ ⊑ ∃<.( ⊓ □¬), to capture the properties of the preference relation. Finally, each occurrence of concept T() in is replaced with concept ⊓ □¬. The encoding is polynomial in the size of and concept satisfiability in LTLTℒ w.r.t. TBoxes is EXPTIME-complete, both with expanding domains and with constant domains. We refer to the extended version [22] for details on the encoding and for a multi-preferential semantics for temporal weighted KBs.

4. Conclusions

In this extended abstract, we have defined a preferential temporal description logics with typicality LTLTℒ . On a different route, a preferential LTL with defeasible temporal operators has been studied in [19, 20], where the decidability of meaningful fragments of the logic is proven, and tableaux based proof methods for such fragments is developed [ 18, 20 ]. Our approach does not consider defeasible temporal operators nor preferences over time points, but combines standard LTL operators with the typicality operator in a temporal ℒ, with preferences over domain elements. Future work includes exploiting the formalism for explainability, following [ 16, 17, 26 ].

Acknowledgements: We thank the anonymous referees for their helpful suggestions. This research was partially supported by Indam-Gncs. Mario Alviano was partially supported by MUR under PNRR project FAIR “Future AI Research”, CUP H23C22000860006 and by LAIA lab. of LIPIcs, 2021. [19] A. Chafik, F. C. Alili, J. Condotta, I. Varzinczak, On the decidability of a fragment of preferential LTL, in: TIME 2020, September 23-25, 2020, Bozen-Bolzano, Italy, volume 178 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. [20] A. Chafik, Defeasible temporal logics for the specification and verification of exceptiontolerant systems, PhD Thesis, Artois University, 2022. [21] L. Giordano, D. Theseider Dupré, Weighted conditional EL⊥ knowledge bases with integer weights: an ASP approach, in: Proc. 37th Int. Conf. on Logic Programming, ICLP 2021 (Technical Communications), Sept. 20-27, 2021, volume 345 of EPTCS, 2021, pp. 70–76. [22] M. Alviano, L. Giordano, D. Theseider Dupré, Preferential temporal description logics with typicality and weighted knowledge bases, in: A. Dovier, A. Formisano (Eds.), Proceedings of the 38th Italian Conference on Computational Logic, Udine, Italy, June 21-23, 2023, volume 3428 of CEUR Workshop Proceedings, CEUR-WS.org, 2023. URL: https://ceur-ws. org/Vol-3428/paper1.pdf. [23] K. Schild, Combining terminological logics with tense logic, in: EPIA, 1993, pp. 105–120. [24] L. Giordano, V. Gliozzi, Encoding a preferential extension of the description logic SROIQ into SROIQ, in: Proc. ISMIS 2015, volume 9384 of LNCS, Springer, 2015, pp. 248–258. [25] R. Booth, G. Casini, T. Meyer, I. Varzinczak, On rational entailment for propositional typicality logic, Artif. Intell. 277 (2019). [26] F. Bartoli, M. Botta, R. Esposito, L. Giordano, D. Theseider Dupré, An asp approach for reasoning about the conditional properties of neural networks: an experiment in the recognition of basic emotions, in: Datalog 2.0 2022: 4th International Workshop on the Resurgence of Datalog in Academia and Industry, September 5, 2022, Genova - Nervi, Italy, volume 3203 of CEUR Workshop Proceedings, CEUR-WS.org, 2022, pp. 54–67. URL: http://ceur-ws.org/Vol-3203/paper4.pdf.

References

[1] C. Lutz , F. Wolter , M. Zakharyaschev , Temporal description logics: A survey , in: TIME , 2008 , pp. 3 - 14 .

[2] A. Artale , R. Kontchakov , A. Kovtunova , V. Ryzhikov , F. Wolter , M. Zakharyaschev , 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, volume 90 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik , 2017 , pp. 1 : 1 - 1 : 37 . doi: 10 .4230/LIPIcs.TIME. 2017 . 1 .

[3] S. Kraus , D. Lehmann , M. Magidor , Nonmonotonic reasoning, preferential models and cumulative logics , Artificial Intelligence 44 ( 1990 ) 167 - 207 .

[4] D. Lehmann , M. Magidor , What does a conditional knowledge base entail? , Artificial Intelligence 55 ( 1992 ) 1 - 60 .

[5] F. Baader , D. Calvanese , D. McGuinness , D. Nardi , P. Patel-Schneider , The Description Logic Handbook - Theory , Implementation, and Applications , Cambridge, 2007 .

[6] K. Britz , J. Heidema , T. Meyer, Semantic preferential subsumption, in: G. Brewka, J. Lang (Eds.), KR 2008 , AAAI Press, Sidney, Australia, 2008 , pp. 476 - 484 .

[7] L. Giordano , V. Gliozzi , N. Olivetti , G. L. Pozzato , ALC+T: a preferential extension of Description Logics , Fundamenta Informaticae 96 ( 2009 ) 1 - 32 .

[8] G. Casini , U. Straccia, Rational Closure for Defeasible Description Logics , in: T. Janhunen, I. Niemelä (Eds.), JELIA 2010 , volume 6341 of LNCS , Springer, Helsinki, 2010 , pp. 77 - 90 .

[9] G. Casini , U. Straccia, Defeasible inheritance-based description logics , Journal of Artificial Intelligence Research (JAIR) 48 ( 2013 ) 415 - 473 .

[10] G. Casini , T. Meyer, I. J. Varzinczak , , K. Moodley , Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox , in: 26th International Workshop on Description Logics (DL 2013 ), volume 1014 of CEUR Workshop Proceedings , 2013 , pp. 600 - 615 .

[11] L. Giordano , V. Gliozzi , N. Olivetti , G. L. Pozzato , Semantic characterization of rational closure: From propositional logic to description logics , Art. Int . 226 ( 2015 ) 1 - 33 .

[12] K. Britz , G. Casini, T. Meyer, K. Moodley, U. Sattler , I. Varzinczak , Principles of klm-style defeasible description logics , ACM Trans. Comput. Log . 22 ( 2021 ) 1: 1 - 1 : 46 .

[13] L. Giordano , V. Gliozzi , A reconstruction of multipreference closure , Artif. Intell . 290 ( 2021 ).

[14] D. J. Lehmann , Another perspective on default reasoning , Ann. Math. Artif. Intell. 15 ( 1995 ) 61 - 82 .

[15] L. Giordano , D. Theseider Dupré , An ASP approach for reasoning in a concept-aware multipreferential lightweight DL , TPLP 10 ( 5 ) ( 2020 ) 751 - 766 .

[16] L. Giordano , D. Theseider Dupré , Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model , in: Proc. JELIA 2021 , May 17-20, volume 12678 of LNCS , Springer, 2021 , pp. 225 - 242 .

[17] L. Giordano , D. Theseider Dupré , An ASP approach for reasoning on neural networks under a finitely many-valued semantics for weighted conditional knowledge bases, Theory Pract . Log. Program. 22 ( 2022 ) 589 - 605 . URL: https://doi.org/10.1017/S1471068422000163.

[18] A. Chafik , F. C. Alili , J. Condotta , I. Varzinczak , A one-pass tree-shaped tableau for defeasible LTL , in: TIME 2021, September 27-29 , 2021 , Klagenfurt, Austria, volume 206