Author name cluster

Patrick Koopmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

AAAI Conference 2026 Conference Paper

Can You Tell the Difference? Contrastive Explanations for ABox Entailments

Patrick Koopmann
Yasir Mahmood
Axel-Cyrille Ngonga Ngomo
Balram Tiwari

We introduce the notion of contrastive ABox explanations to answer questions of the type “Why is a an instance of C, but b is not?”. While there are various approaches for explaining positive entailments (why is C(a) entailed by the knowledge base) as well as missing entailments (why is C(b) not entailed) in isolation, contrastive explanations consider both at the same time, which allows them to focus on the relevant commonalities and differences between a and b. We develop an appropriate notion of contrastive explanations for the special case of ABox reasoning with description logic ontologies, and analyze the computational complexity for different variants under different optimality criteria, considering lightweight as well as more expressive description logics. We implemented a first method for computing one variant of contrastive explanations, and evaluated it on generated problems for realistic knowledge bases.

PDF Details DOI

KR Conference 2024 System Paper

Explaining Reasoning Results for OWL Ontologies with Evee

Christian Alrabbaa
Stefan Borgwardt
Tom Friese
Anke Hirsch
Nina Knieriemen
Patrick Koopmann
Alisa Kovtunova
Antonio Krüger

One of the advantages of formalizing domain knowledge in OWL ontologies is that one can use reasoning systems to infer implicit information automatically. However, it is not always straightforward to understand why certain entailments are inferred, and others are not. The popular ontology editor Protégé offers two explanation services to deal with this issue: justifications for OWL 2 DL ontologies, and proofs generated by the reasoner ELK for lightweight OWL 2 EL ontologies. Since justifications are often insufficient for explaining inferences, there is thus only little tool support for more comprehensive explanations in expressive ontology languages, and there is no tool support at all to explain why something was not derived. In this paper, we present Evee, a Java library and a collection of plug-ins for Protégé that offers advanced explanation services for both inferred and missing entailments. Evee explains inferred entailments using proofs in description logics up to ALCH. Missing entailments can be explained using counterexamples and abduction. We evaluated the effectiveness and the interface design of our plug-ins with description logic experts, ontology engineers, and students in two user studies. In these experiments, we were able to not only validate the tool but also gather feedback and insights to improve the existing designs.

PDF Details DOI

ECAI Conference 2024 Conference Paper

Planning with OWL-DL Ontologies

Tobias John
Patrick Koopmann

We introduce ontology-mediated planning, in which planning problems are combined with an ontology. Our formalism differs from existing ones in that we focus on a strong separation of the formalisms for describing planning problems and ontologies, which are only losely coupled by an interface. Moreover, we present a black-box algorithm that supports the full expressive power of OWL DL. This goes beyond what existing approaches combining automated planning with ontologies can do, which only support limited description logics such as DL-Lite and description logics that are Horn. Our main algorithm relies on rewritings of the ontology-mediated planning specifications into PDDL, so that existing planning systems can be used to solve them. The algorithm relies on justifications, which allows for a generic approach that is independent of the expressivity of the ontology language. However, dedicated optimizations for computing justifications need to be implemented to enable an efficient rewriting procedure. We evaluated our implementation on benchmark sets from several domains. The evaluation shows that our procedure works in practice and that tailoring the reasoning procedure has significant impact on the performance.

Details

NMR Workshop 2024 Conference Paper

Using ADFs for Inconsistency-Tolerant Query Answering with Existential Rules

Atefeh Keshavarzi Zafarghandi
Patrick Koopmann

We present a new reduction of inconsistency-tolerant query answering to acceptance in ADFs. In particular, we consider knowledge bases (KBs) that use existential rules, and consider common inconsistency-tolerant semantics based on maximal consistent subsets. While reductions of inconsistency-tolerant reasoning to argumentation frameworks have been considered before, we aim to obtain a reduction that reflects the inference structure of the KB on a fine-grained level, so that they can be used to explain query answers on the level of individual inference steps. In particular, in our ADFs, every node corresponds to a fact derived in the chase, and acceptance conditions are used to relate facts using inference rules and integrity constraints. We show that our reduction satisfies rationality postulates, and observe that common semantics of ADFs fail to fully reproduce inconsistency-tolerant query answering with our reduction. We introduce a new semantics as refinement of the preferred semantics, which solves this problem, and analyze the computational complexity of this new semantics in the general and in our case.

Details

IJCAI Conference 2023 Conference Paper

Efficient Computation of General Modules for ALC Ontologies

Hui Yang
Patrick Koopmann
Yue Ma
Nicole Bidoit

We present a method for extracting general modules for ontologies formulated in the description logic ALC. A module for an ontology is an ideally substantially smaller ontology that preserves all entailments for a user-specified set of terms. As such, it has applications such as ontology reuse and ontology analysis. Different from classical modules, general modules may use axioms not explicitly present in the input ontology, which allows for additional conciseness. So far, general modules have only been investigated for lightweight description logics. We present the first work that considers the more expressive description logic ALC. In particular, our contribution is a new method based on uniform interpolation supported by some new theoretical results. Our evaluation indicates that our general modules are often smaller than classical modules and uniform interpolants computed by the state-of-the-art, and compared with uniform interpolants, can be computed in significantly shorter time. Moreover, our method can be used for, and in fact, improves the computation of uniform interpolants and classical modules.

PDF Details DOI

JELIA Conference 2023 Invited Paper

Optimal Repairs in the Description Logic E ℒ Revisited

Franz Baader
Patrick Koopmann
Francesco Kriegel

Abstract Ontologies based on Description Logics may contain errors, which are usually detected when reasoning produces consequences that follow from the ontology, but do not hold in the modelled application domain. In previous work, we have introduced repair approaches for $\mathcal{E}\mathcal{L}$ ontologies that are optimal in the sense that they preserve a maximal amount of consequences. In this paper, we will, on the one hand, review these approaches, but with an emphasis on motivation rather than on technical details. On the other hand, we will describe new results that address the problems that optimal repairs may become very large or need not even exist unless strong restrictions on the terminological part of the ontology apply. We will show how one can deal with these problems by introducing concise representations of optimal repairs.

Details

IJCAI Conference 2021 Conference Paper

Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics

Patrick Koopmann

Given a knowledge base and an observation as a set of facts, ABox abduction aims at computing a hypothesis that, when added to the knowledge base, is sufficient to entail the observation. In signature-based ABox abduction, the hypothesis is further required to use only names from a given set. This form of abduction has applications such as diagnosis, KB repair, or explaning missing entailments. It is possible that hypotheses for a given observation only exist if we admit the use of fresh individuals and/or complex concepts built from the given signature, something most approaches for ABox abduction so far do not allow or only allow with restrictions. In this paper, we investigate the computational complexity of this form of abduction---allowing either fresh individuals, complex concepts, or both---for various description logics, and give size bounds on the hypotheses if they exist.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Deductive Module Extraction for Expressive Description Logics

Patrick Koopmann
Jieying Chen

In deductive module extraction, we determine a small subset of an ontology for a given vocabulary that preserves all logical entailments that can be expressed in that vocabulary. While in the literature stronger module notions have been discussed, we argue that for applications in ontology analysis and ontology reuse, deductive modules, which are decidable and potentially smaller, are often sufficient. We present methods based on uniform interpolation for extracting different variants of deductive modules, satisfying properties such as completeness, minimality and robustness under replacements, the latter being particularly relevant for ontology reuse. An evaluation of our implementation shows that the modules computed by our method are often significantly smaller than those computed by existing methods.

PDF Details DOI

LPAR Conference 2020 Conference Paper

Finding Small Proofs for Description Logic Entailments: Theory and Practice

Christian Alrabbaa
Franz Baader
Stefan Borgwardt
Patrick Koopmann
Alisa Kovtunova

Logic-based approaches to AI have the advantage that their behaviour can in principle be explained by providing their users with proofs for the derived consequences. However, if such proofs get very large, then it may be hard to understand a consequence even if the individual derivation steps are easy to comprehend. This motivates our interest in finding small proofs for Description Logic (DL) entailments. Instead of concentrating on a specific DL and proof calculus for this DL, we introduce a general framework in which proofs are represented as labeled, directed hypergraphs, where each hyperedge corresponds to a single sound derivation step. On the theoretical side, we investigate the complexity of deciding whether a certain consequence has a proof of size at most n along the following orthogonal dimensions: (i) the underlying proof system is polynomial or exponential; (ii) proofs may or may not reuse already derived consequences; and (iii) the number n is represented in unary or binary. We have determined the exact worst-case complexity of this decision problem for all but one of the possible combinations of these options. On the practical side, we have developed and implemented an approach for generating proofs for expressive DLs based on a non-standard reasoning task called forgetting. We have evaluated this approach on a set of realistic ontologies and compared the obtained proofs with proofs generated by the DL reasoner ELK, finding that forgetting-based proofs are often better w. r. t. different measures of proof complexity.

Details

KR Conference 2020 Conference Paper

Signature-Based Abduction for Expressive Description Logics

Patrick Koopmann
Warren Del-Pinto
Sophie Tourret
Renate A. Schmidt

Signature-based abduction aims at building hypotheses over a specified set of names, the signature, that explain an observation relative to some background knowledge. This type of abduction is useful for tasks such as diagnosis, where the vocab- ulary used for observed symptoms differs from the vocabulary expected to explain those symptoms. We present the first complete method solving signature-based abduction for observations expressed in the expressive description logic ALC, which can include TBox and ABox axioms. The method is guaranteed to compute a finite and complete set of hypotheses, and is evaluated on a set of realistic knowledge bases.

PDF Details DOI

AAAI Conference 2019 Conference Paper

From Horn-SRIQ to Datalog: A Data-Independent Transformation That Preserves Assertion Entailment

David Carral
Larry González
Patrick Koopmann

Ontology-based access to large data-sets has recently gained a lot of attention. To access data efficiently, one approach is to rewrite the ontology into Datalog, and then use powerful Datalog engines to compute implicit entailments. Existing rewriting techniques support Description Logics (DLs) from ELH to Horn-SHIQ. We go one step further and present one such data-independent rewriting technique for Horn-SRIQu, the extension of Horn-SHIQ that supports role chain axioms, an expressive feature prominently used in many real-world ontologies. We evaluated our rewriting technique on a large known corpus of ontologies. Our experiments show that the resulting rewritings are of moderate size, and that our approach is more efficient than state-of-the-art DL reasoners when reasoning with data-intensive ontologies.

PDF Details

AAAI Conference 2019 Conference Paper

Ontology-Based Query Answering for Probabilistic Temporal Data

Patrick Koopmann

We investigate ontology-based query answering for data that are both temporal and probabilistic, which might occur in contexts such as stream reasoning or situation recognition with uncertain data. We present a framework that allows to represent temporal probabilistic data, and introduce a query language with which complex temporal and probabilistic patterns can be described. Specifically, this language combines conjunctive queries with operators from linear time logic as well as probability operators. We analyse the complexities of evaluating queries in this language in various settings. While in some cases, combining the temporal and the probabilistic dimension in such a way comes at the cost of increased complexity, we also determine cases for which this increase can be avoided.

PDF Details

AAAI Conference 2017 Conference Paper

Small Is Beautiful: Computing Minimal Equivalent EL Concepts

Nadeschda Nikitina
Patrick Koopmann

In this paper, we present an algorithm and a tool for computing minimal, equivalent EL concepts wrt. a given ontology. Our tool can provide valuable support in manual development of ontologies and improve the quality of ontologies automatically generated by processes such as uniform interpolation, ontology learning, rewriting ontologies into simpler DLs, abduction and knowledge revision. Deciding whether there exist equivalent EL concepts of size less than k is known to be an NP-complete problem. We propose a minimisation algorithm that achieves reasonable computational performance also for larger ontologies and complex concepts. We evaluate our tool on several bio-medical ontologies with promising results.

PDF Details

AAAI Conference 2015 Conference Paper

Uniform Interpolation and Forgetting for ALC Ontologies with ABoxes

Patrick Koopmann
Renate Schmidt

Uniform interpolation and the dual task of forgetting restrict the ontology to a specified subset of concept and role names. This makes them useful tools for ontology analysis, ontology evolution and information hiding. Most previous research focused on uniform interpolation of TBoxes. However, especially for applications in privacy and information hiding, it is essential that uniform interpolation methods can deal with ABoxes as well. We present the first method that can compute uniform interpolants of any ALC ontology with ABoxes. ABoxes bring their own challenges when computing uniform interpolants, possibly requiring disjunctive statements or nominals in the resulting ABox. Our method can compute representations of uniform interpolants in ALCO. An evaluation on realistic ontologies shows that these uniform interpolants can be practically computed, and can often even be presented in pure ALC.

PDF Details

LPAR Conference 2013 Conference Paper

Forgetting Concept and Role Symbols in $\mathcal{ALCH}$ -Ontologies

Patrick Koopmann
Renate A. Schmidt

Abstract We develop a resolution-based method for forgetting concept and role symbols in $\mathcal{ALCH}$ ontologies, or for computing uniform interpolants in $\mathcal{ALCH}$. Uniform interpolants use only a restricted set of symbols, while preserving logical consequences of the original ontology involving these symbols. While recent work towards practical methods for uniform interpolation in expressive description logics limits attention to forgetting concept symbols, we believe most applications would benefit from the possibility to forget both role and concept symbols. We focus on the description logic $\mathcal{ALCH}$, which allows for the formalisation of role hierarchies. Our approach is based on a recently developed resolution-based calculus for forgetting concept symbols in $\mathcal{ALC}$ ontologies, which we extend by redundancy elimination techniques to make it practical for larger ontologies. Experiments on $\mathcal{ALCH}$ fragments of real life ontologies suggest that our method is applicable in a lot of real-life applications.

Details