=Paper=
{{Paper
|id=Vol-3263/abstract-6
|storemode=property
|title=Reasoning on Multi-Relational Contextual Hierarchies via Answer Set Programming with Algebraic Measures (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3263/abstract-6.pdf
|volume=Vol-3263
|authors=Loris Bozzato,Thomas Eiter,Rafael Kiesel
|dblpUrl=https://dblp.org/rec/conf/dlog/BozzatoEK22
}}
==Reasoning on Multi-Relational Contextual Hierarchies via Answer Set Programming with Algebraic Measures (Extended Abstract)==
https://ceur-ws.org/Vol-3263/abstract-6.pdf
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.