Reasoning on Multi-Relational Contextual Hierarchies via Answer Set Programming with Algebraic Measures Extended Abstract Loris Bozzato1 , Thomas Eiter2 and Rafael Kiesel2 1 Fondazione Bruno Kessler, Via Sommarive 18, 38123 Trento, Italy 2 Technische Universität Wien, Favoritenstraße 9-11, A-1040 Vienna, Austria Abstract This extended abstract summarizes our previous work on a defeasible extension of Description Logic (DL) for contextual reasoning.1 Here, we considered on the one hand the addition of multiple dimensions of defeasibility, allowing us to express for example that a rule has to be satisfied no matter the geographical context but that the rule can change in the next years. On the other hand, we showed that Answer Set Programming (ASP) especially when enhanced with algebraic measures provide a powerful tool to implement our framework and open up perspectives for the future. Keywords Defeasible Knowledge, Description Logics, ASP, Algebraic Measures, Justifiable Exceptions 1. Introduction Reasoning with context dependent knowledge is a classical and fundamental theme in AI [2, 3]. Recently, it has gained increasing attention for the Semantic Web as knowledge resources must be interpreted with contextual information from their metadata. Thus, several approaches have been developed for contextual reasoning [4, 5, 6], mostly based on description logics. A rich framework among them are Contextualized Knowledge Repositories (CKR) [6]: CKR knowledge bases (KBs) are 2-layered structures with a global context, which contains context- independent global knowledge and meta-knowledge about the structure of the KB, and local contexts containing knowledge about specific situations (e.g., a region in space, a site of an organization). The global knowledge is propagated to local contexts, where inherited axioms may be defeasible, meaning that instances can be “overridden” on an exceptional basis [7]. Reasoning from CKRs strongly links to logic programming and Answer Set Programming (ASP), as the KBs are over a Horn-description logic and the working of defeasible axioms was inspired by conflict handling in inheritance logic programs [8]. Furthermore, answering instance and conjunctive queries is possible via a uniform ASP program that employs a materialization calculus [9]. 1 The paper [1] has been presented at the 37th International Conference on Logic Programming (ICLP 2021). DL 2022: 35th International Workshop on Description Logics, August 7–10, 2022, Haifa, Israel " bozzato@fbk.eu (L. Bozzato); thomas.eiter@tuwien.ac.at (T. Eiter); rafael.kiesel@tuwien.ac.at (R. Kiesel)  0000-0003-1757-9859 (L. Bozzato); 0000-0001-6003-6345 (T. Eiter); 0000-0002-8866-3452 (R. Kiesel) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 𝑐world : 𝑐world_2019 : 𝐸⊓𝑅⊑⊥ 𝐸⊓𝑅⊑⊥ 𝑐world_2020 : 𝑐world_2021 : D(𝑆 ⊑ 𝐸) D𝑐 (𝑆 ⊑ 𝐸) 𝑐branch : 𝑐branch_2019 : 𝑐branch_2020 : 𝑂𝑆 ⊓ 𝑅𝐸 ⊑ ⊥ 𝑂𝑆 ⊓ 𝑅𝐸 ⊑ ⊥ D𝑐 (𝑆 ⊑ 𝑅) 𝑐branch_2021 : 𝑆 ⊑ 𝑂𝑆 D𝑡 (𝑆 ⊑ 𝑂𝑆) D𝑡 (𝑆 ⊑ 𝑅𝐸) D(𝑆 ⊑ 𝑅) 𝑐local_2019 : 𝑐local_2020 : 𝑐local_2021 : 𝑐local : 𝑆(𝑖) 𝑆(𝑖) Figure 1: Two CKRs, the left with a single relation, the right one is multi-relational. Both model properties of employees in a company in different contexts. For modeling and analyzing complex scenarios where global regulations can be refined by more specific situations, the CKR model was extended in [10] to cater for defeasible axioms in local contexts and knowledge inheritance across hierarchies, based on a coverage contextual relation [6]. Here, coverage means that one context may be more specific than another: thus, defeasible axioms from a general context can be overridden in a covered context that represents a more specific situation. Example 1. In the left CKR in Figure 1, we model the employees of a company on three different contextual levels, the world, a branch and a local site. There are people working in Electronics (𝐸), Robotics (𝑅) or as a Supervisor (𝑆). They can work either onsite (𝑂𝑆) or remote (𝑅𝐸). At the global level, supervisors should (by default) work in electronics. This is overwritten (by default) in the branch, where supervisors should work in robotics. Therefore, the supervisor 𝑖 at the local context satisfies 𝑆(𝑖), 𝑂𝑆(𝑖) and 𝑅(𝑖), but not 𝐸(𝑖). This approach, however, is limited to reason only on hierarchies based on this single type of contextual relation. In practice, defeasible inheritance may be necessary under different contextual relations. For instance, in our example, we may want to specify that 𝑆 ⊑ 𝑂𝑆 is actually defeasible w.r.t. time and D(𝑆 ⊑ 𝑅) actually only holds since 2020. As the following extension of the example shows, this shortcoming can be approached by introducing multi-relational CKRs. Example 2 (cont.). Consider the multi-relational CKR given on the right in Figure 1. Here, denotes the coverage relation, and denotes the time relation. Note also that axioms are not generally defeasible anymore, but only with respect to either coverage or time, denoted by D𝑐 and D𝑡 , respectively. Given the adopted model, we can correctly derive that in 2019 at the local context we still have 𝐸(𝑖) instead of 𝑅(𝑖). This changes in the years 2020 and 2021, where we have 𝑅(𝑖) due to the defeasible axiom D𝑐 (𝑆 ⊑ 𝑅) at context 𝑐local_2020 . Here, we also model that until the current context changes with respect to time, supervisors need to work remotely using the axiom D𝑡 (𝑆 ⊑ 𝑅𝐸). Thus, we have 𝑅𝐸(𝑖) instead of 𝑂𝑆(𝑖) in 2020 and 2021. A further limitation is that even for a single coverage relation, it is challenging to encode the induced preference relation over CKR interpretations using ASP because the relation may not be a strict partial order. By default, this is as assumed e.g. in the asprin framework [11] and dropping this assumption in asprin leads to an increase in complexity. A specialized implementation for preferential reasoning was introduced [12], which however needs to consider all answer sets of a program to single out a preferred CKR model. We showed that we can overcome the first limitation by presenting a multi-relational version of the CKR framework. The second limitation was attacked by encoding reasoning with preferences in a recent extension of ASP with algebraic measures. 2. Contributions We made the following contributions: • We generalized single-relational CKRs to multi-relational CKRs (MR-CKR), where axioms are not defeasible in general but merely with regard to individual relations that model coverage along different dimensions such as time or location. By a combination of preferences over the distinct individual relations, we obtain an overall preference over the models of a CKR. • We showed how to model multi-relation CKRs in ASP. Specifically, we use to this end ASP with algebraic measures [13], which is a foundation to express many quantitative reasoning problems. Here, weighted logic formulas [14] measure values associated with an interpretation ℐ by performing a computation over a semiring, whose outcome depends on the truth of the propositional variables in ℐ. Such measures can be used for e.g. weighted model counting, probabilistic reasoning and, as in our case, preferential reasoning. • While asprin is a powerful tool for modeling preferences in ASP, it appears to be ill- suited for expressing multi-relational CKR. The reason are eval-expressions in CKRs, which propagate predicate extensions from one local context to another. We showed, however, that under a well-behaved use of such expressions (according to a syntactic disconnectedness condition), multi-relational CKRs can be expressed efficiently in asprin. This enables us to use the asprin solver to evaluate preferences for CKRs, which we showcased in a prototype implementation. • Furthermore, ASP with algebraic measures opens up the possibility of reasoning tasks for CKRs beyond asprin’s capability, even in absence of eval-expression. As examples, we consider obtaining preferred CKR models by overall weight queries and epistemic reasoning, which for description logics is specifically needed in aggregate queries [15]. 3. Discussion and Conclusion We considered the application of ASP with algebraic measures for expressing preferences of defeasibility in multirelational CKRs. Specifically, we found special cases in which asprin can be used for efficient reasoning and explored advanced reasoning scenarios, where the expressivity and flexibility of algebraic measures offers an advantage. We plan to further study the possibilities for epistemic reasoning on DLs enabled by algebraic measures. With respect to contextual reasoning, a possible continuation of this work may consider a refinement of the definitions of preference and knowledge propagation across different contextual relations, possibly moving towards non-Horn DLs in contexts [16]. Apart from further theoretical aspects, we plan to consider a motivating real-world application. Acknowledgments This work was partially supported by the European Commission funded projects “Humane AI: Toward AI Systems That Augment and Empower Humans by Understanding Us, our Society and the World Around Us” (grant #820437) and “AI4EU: A European AI on Demand Platform and Ecosystem” (grant #825619), and the Austrian Science Fund (FWF) project W1255-N23. The support is gratefully acknowledged. References [1] L. Bozzato, T. Eiter, R. Kiesel, Reasoning on multirelational contextual hierarchies via answer set programming with algebraic measures, Theory and Practice of Logic Program- ming 21 (2021) 593–609. URL: https://doi.org/10.1017/S1471068421000284. doi:10.1017/ S1471068421000284. [2] J. McCarthy, Notes on formalizing context, in: R. Bajcsy (Ed.), Proceedings of the 13th International Joint Conference on Artificial Intelligence. Chambéry, France, August 28 - September 3, 1993, Morgan Kaufmann, 1993, pp. 555–562. URL: http://www-formal. stanford.edu/jmc/context3/context3.html. [3] F. Giunchiglia, L. Serafini, Multilanguage hierarchical logics, or: how we can do without modal logics, Artificial Intelligence 65 (1994) 29–70. [4] U. Straccia, N. Lopes, G. Lukácsy, A. Polleres, A general framework for representing and reasoning with annotated semantic web data, in: M. Fox, D. Poole (Eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, AAAI Press, 2010. URL: http://www.aaai.org/ocs/index. php/AAAI/AAAI10/paper/view/1590. [5] S. Klarman, Reasoning with Contexts in Description Logics, Ph.D. thesis, Free University of Amsterdam, 2013. [6] L. Serafini, M. Homola, Contextualized knowledge repositories for the semantic web, Journal of Web Semantics 12 (2012) 64–87. [7] L. Bozzato, T. Eiter, L. Serafini, Enhancing context knowledge repositories with justifiable exceptions, Artificial Intelligence 257 (2018) 72–126. [8] F. Buccafurri, W. Faber, N. Leone, Disjunctive logic programs with inheritance, in: D. D. Schreye (Ed.), Logic Programming: The 1999 International Conference (ICLP 1999), MIT Press, 1999, pp. 79–93. [9] M. Krötzsch, Efficient inferencing for OWL EL, in: T. Janhunen, I. Niemelä (Eds.), Logics in Artificial Intelligence - 12th European Conference, JELIA 2010, Helsinki, Finland, September 13-15, 2010. Proceedings, volume 6341 of Lecture Notes in Computer Science, Springer, 2010, pp. 234–246. URL: https://doi.org/10.1007/978-3-642-15675-5_21. doi:10. 1007/978-3-642-15675-5\_21. [10] L. Bozzato, L. Serafini, T. Eiter, Reasoning with justifiable exceptions in contextual hier- archies, in: M. Thielscher, F. Toni, F. Wolter (Eds.), Principles of Knowledge Represen- tation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018, AAAI Press, 2018, pp. 329–338. URL: https://aaai.org/ocs/index.php/KR/KR18/paper/view/18032. [11] G. Brewka, J. P. Delgrande, J. Romero, T. Schaub, asprin: Customizing answer set prefer- ences without a headache, in: B. Bonet, S. Koenig (Eds.), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, AAAI Press, 2015, pp. 1467–1474. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/ view/9535. [12] L. Bozzato, T. Eiter, L. Serafini, Justifiable exceptions in general contextual hierarchies, in: G. Bella, P. Bouquet (Eds.), Modeling and Using Context. CONTEXT 2019, volume 11939 of Lecture Notes in Computer Science, Springer, 2019, pp. 26–39. doi:10.1007/ 978-3-030-34974-5\_3. [13] T. Eiter, R. Kiesel, Weighted LARS for quantitative stream reasoning, in: G. D. Giacomo, A. Catalá, B. Dilkina, M. Milano, S. Barro, A. Bugarín, J. Lang (Eds.), ECAI 2020 - 24th European Conference on Artificial Intelligence, 29 August-8 September 2020, Santiago de Compostela, Spain, August 29 - September 8, 2020 - Including 10th Conference on Prestigious Applications of Artificial Intelligence (PAIS 2020), volume 325 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2020, pp. 729–736. URL: https://doi.org/ 10.3233/FAIA200160. doi:10.3233/FAIA200160. [14] M. Droste, P. Gastin, Weighted automata and weighted logics, in: L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, Springer, 2005, pp. 513–525. URL: https://doi.org/10.1007/11523468_42. doi:10.1007/11523468\_42. [15] D. Calvanese, E. Kharlamov, W. Nutt, C. Thorne, Aggregate queries over ontologies, in: Proceedings of the 2nd International Workshop on Ontologies and Information Systems for the Semantic Web (ONISW 2008), Association for Computing Machinery, New York, NY, USA, 2008, pp. 97–104. URL: https://doi.org/10.1145/1458484.1458500. doi:10.1145/ 1458484.1458500. [16] L. Bozzato, T. Eiter, L. Serafini, Reasoning with Justifiable Exceptions in ℰℒ⊥ Contextual- ized Knowledge Repositories, in: Description Logic, Theory Combination, and All That, volume 11560 of LNCS, Springer, 2019, pp. 110–134.