Building and mantaining large-scale ontologies is an error-prone task. It is thus not uncommon to find unwanted or unexpected consequences that follow implicitely from the restrictions in the ontology. To understand and correct these consequences, it is helpful to find the specific portions of the ontology that are responsible for them. Axiom-pinpointing is the task of finding minimal subontologies that entail a given consequence, also called MinAs. In this work we look at the task of computing all the MinAs by means of modified decision procedures. We first show that tableaux- and automata-based decision procedures can be transformed into pinpointing algorithms that output a (compact) representation of the set of all MinAs. We then explore the complexity of the problem.

Building and mantaining large-scale ontologies is an error-prone task. It is thus not uncommon to find unwanted or unexpected consequences that follow implicitely from the restrictions in the ontology. To understand and correct these consequences, it is helpful to find the specific portions of the ontology that are responsible for them. Axiom-pinpointing is the task of finding minimal subontologies that entail a given consequence, also called MinAs. In this work we look at the task of computing all the MinAs by means of modified decision procedures. We first show that tableaux- and automata-based decision procedures can be transformed into pinpointing algorithms that output a (compact) representation of the set of all MinAs. We then explore the complexity of the problem.

IT-relaterad brottslighet ökar lavinartat och Polismyndigheten står inför nya utmaningar i att identifiera gärningsmän. Allt mer mjukvaror och tjänster blir automatiserade och det gäller även mjukvarorna som Polismyndigheten använder sig av. En av utmaningarna är den oerhörda mängd data som måste processas och analyseras i undersökningar och då förutsätts det att verktygen presenterar data med bibehållen integritet. Verktygen som används är nästan alltid tredjepartsmjukvara och då är det viktigt att rätt data plockas ut och att datan är korrekt. Denna studie har som mål att jämföra två mjukvaror i hur de identifierar och presenterar data. Studien görs i samverkan med Polismyndigheten vid Regionalt IT-brottscentrum Väst – Skövde och hoppas inbringa nya insikter och kunskaper i de verktyg som jämförelsen grundas på och med hjälp av kunskaperna kunna värdesätta integriteten hos verktygen. Resultatet som framträder i studien är att verktygen presenterar data med bibehållen integritet. / Cybercrime is on the rise in society and the Swedish Police is facing new challenges in identifying criminals. More tools and services are becoming automated, and this also applies to the tools that the Swedish Police uses. One of the challenges is the enormous amount of data that must be processed and analyzed during investigations. The tools used are always third-party programs and IT-forensics needs to rely on the organization that makes the software. This study aims to evaluate two different tools in how they identify and present artifacts. The study is conducted in collaboration with the Police Authority at the Regional IT Crime Center West - Skövde and hopes to bring new insights and knowledge into the tools on which the comparison is based on and with the help of the knowledge be able to value the integrity of the tools. The result that the study presents is that the tools are presenting data with preserved integrity.

Axiom pinpointing has been introduced in description logics (DLs) to help the used understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in consideration. Several pinpointing algorithms have been described as extensions of the standard tableau-based reasoning algorithms for deciding consequences from DL knowledge bases. Although these extensions are based on similar ideas, they are all introduced for a particular tableau-based algorithm for a particular DL, using specific traits of them. In the past, we have developed a general approach for extending tableau-based algorithms into pinpointing algorithms. In this paper we explore some issues of termination of general tableaux and their pinpointing extensions. We also define a subclass of tableaux that allows the use of so-called blocking conditions, which stop the execution of the algorithm once a pattern is found, and adapt the pinpointing extensions accordingly, guaranteeing its correctness and termination.

Consider an ontology T where every axiom is labeled with an element of a lattice (L, ≤). Then every element l of L determines a sub-ontology Tl, which consists of the axioms of T whose labels are greater or equal to l. These labels may be interpreted as required access rights, in which case Tl is the sub-ontology that a user with access right l is allowed to see, or as trust levels, in which case Tl consists of those axioms that we trust with level at least l. Given a consequence α (such as a subsumption relationship between concepts) that follows from the whole ontology T, we want to know from which of the sub-ontologies Tl determined by lattice elements l the consequence α still follows. However, instead of reasoning with Tl in the deployment phase of the ontology, we want to pre-compute this information during the development phase. More precisely, we want to compute what we call a boundary for α, i.e., an element μα of L such that α follows from T l iff l ≤ μα. In this paper we show that, under certain restrictions on the elements l used to define the sub-ontologies, such a boundary always exists, and we describe black-box approaches for computing it that are generalizations of approaches for axiom pinpointing in description logics. We also present first experimental results that compare the efficiency of these approaches on real-world ontologies.

In the area of Description Logic (DL) based knowledge representation, research on reasoning w.r.t. general terminologies has mainly focused on very expressive DLs. Recently, though, it was shown for the DL EL, providing only the constructors conjunction and existential restriction, that the subsumption problem w.r.t. cyclic terminologies can be decided in polynomial time, a surprisingly low upper bound. In this paper, we show that even admitting general concept inclusion (GCI) axioms and role hierarchies in EL terminologies preserves the polynomial time upper bound for subsumption. We also show that subsumption becomes co-NP hard when adding one of the constructors number restriction, disjunction, and `allsome', an operator used in the DL k-rep. An interesting implication of the first result is that reasoning over the widely used medical terminology snomed is possible in polynomial time.

Motivated by medical terminology applications, we investigate the decidability of an expressive and prominent DL, SHIQ, extended with role inclusion axioms of the form RoS⊑T. It is well-known that a naive such extension leads to undecidability, and thus we restrict our attention to axioms of the form RoS⊑R or SoR⊑R, which is the most important form of axioms in the applications that motivated this extension. Surprisingly, this extension is still undecidable. However, it turns out that restricting our attention further to acyclic sets of such axioms, we regain decidability. We present a tableau-based decision procedure for this DL and report on its implementation, which behaves well in practise and provides important additional functionality in a medical terminology application.

The classical approach for repairing a Description Logic ontology O in the sense of removing an unwanted consequence α is to delete a minimal number of axioms from O such that the resulting ontology O´ does not have the consequence α. However, the complete deletion of axioms may be too rough, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem, we propose a more gentle way of repair in which axioms are not necessarily deleted, but only weakened. On the one hand, we investigate general properties of this gentle repair method. On the other hand, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic EL.

Aus der Einleitung: Description Logics (DLs) are a family of knowledge representation formalisms that are successfully applied in many application domains. They provide the logical foundation for the Direct Semantics of the standard web ontology language OWL2. The light-weight DL EL, underlying the OWL2 EL profile, is of particular interest since all common reasoning problems are polynomial in this logic, and it is used in many prominent biomedical ontologies like SNOMEDCT and the Gene Ontology.

Aus der Einleitung: Description Logics (DLs) [BCM+07] are popular knowledge representation formalisms, mainly because they are the basis of the standardized OWL 2 Direct Semantics, their expressiveness can be tailored to the application at hand, and many optimized reasoning systems are available.