Constructing description logic ontologies is a difficult task that is normally conducted by experts. Recent results show that parts of ontologies can be constructed from description logic interpretations. However, these results assume the interpretations to be free of errors, which may not be the case for real-world data. To provide some mechanism to handle these errors, the notion of confidence from data mining is introduced into description logics, yielding confident general concept inclusions (confident GCIs) of finite interpretations. The main focus of this work is to prove the existence of finite bases of confident GCIs and to describe some of theses bases explicitly.

The World Wide Web contains large amounts of data and in most cases this data is without any explicit structure. The lack of structure makes it difficult for automated agents to understand and use such data. A step towards a more structured World Wide Web is the idea of the Semantic Web which aims at introducing semantics to data on the World Wide Web. One of the key technologies in this endeavour are ontologies which provide means for modeling a domain of interest. Developing and maintaining ontologies is not an easy task and it is often the case that defects are introduced into ontologies. This can be a problem for semantically-enabled applications such as ontology-based querying. Defects in ontologies directly influence the quality of the results of such applications as correct results can be missed and wrong results can be returned. This thesis considers one type of defects in ontologies, namely the problem of completing the is-a structure in ontologies represented in description logics. We focus on two variants of description logics, the EL family and ALC, which are often used in practice. The contributions of this thesis are as follows. First, we formalize the problem of completing the is-a structure as a generalized TBox abduction problem (GTAP) which is a new type of abduction problem in description logics. Next, we provide algorithms for solving GTAP in the EL family and ALC description logics. Finally, we describe two implemented systems based on the introduced algorithms. The systems were evaluated in two experiments which have shown the usefulness of our approach. For example, in one experiment using ontologies from the Ontology Alignment Evaluation Initiative 58 and 94 detected missing is-a relations were repaired by adding 54 and 101 is-a relations, respectively, introducing new knowledge to the ontologies.

In a modern world software systems are literally everywhere. These should cope with very complex scenarios including the ability of context-awareness and self-adaptability. The concept of roles provide the means to model such complex, context-dependent systems. In role-based systems, the relational and context-dependent properties of objects are transferred into the roles that the object plays in a certain context. However, even if the domain can be expressed in a well-structured and modular way, role-based models can still be hard to comprehend due to the sophisticated semantics of roles, contexts and different constraints. Hence, unintended implications or inconsistencies may be overlooked. A feasible logical formalism is required here. In this setting Description Logics (DLs) fit very well as a starting point for further considerations since as a decidable fragment of first-order logic they have both an underlying formal semantics and decidable reasoning problems. DLs are a well-understood family of knowledge representation formalisms which allow to represent application domains in a well-structured way by DL-concepts, i.e. unary predicates, and DL-roles, i.e. binary predicates. However, classical DLs lack expressive power to formalise contextual knowledge which is crucial for formalising role-based systems. We investigate a novel family of contextualised description logics that is capable of expressing contextual knowledge and preserves decidability even in the presence of rigid DL-roles, i.e. relational structures that are context-independent. For these contextualised description logics we thoroughly analyse the complexity of the consistency problem. Furthermore, we present a mapping algorithm that allows for an automated translation from a formal role-based model, namely a Compartment Role Object Model (CROM), into a contextualised DL ontology. We prove the semantical correctness and provide ideas how features extending CROM can be expressed in our contextualised DLs. As final step for a completely automated analysis of role-based models, we investigate a practical reasoning algorithm and implement the first reasoner that can process contextual ontologies.

Description logics (DL) knowledge bases are often build by users with expertise in the application domain, but little expertise in logic. To support this kind of users when building their knowledge bases a number of extension methods have been proposed to provide the user with concept descriptions as a starting point for new concept definitions. The inference service central to several of these approaches is the computation of (least) common subsumers of concept descriptions. In case disjunction of concepts can be expressed in the DL under consideration, the least common subsumer (lcs) is just the disjunction of the input concepts. Such a trivial lcs is of little use as a starting point for a new concept definition to be edited by the user. To address this problem we propose two approaches to obtain "meaningful" common subsumers in the presence of disjunction tailored to two different methods to extend DL knowledge bases. More precisely, we devise computation methods for the approximation-based approach and the customization of DL knowledge bases, extend these methods to DLs with number restrictions and discuss their efficient implementation.

El razonamiento y cambio de bases de conocimiento o knowledge bases (KBs) por sobre las inconsistencias, es de extrema importancia en áreas como la medicina y el derecho. Esto es, razonar y provocar la evolucion del conocimiento sin necesidad de restaurar la consistencia, sino proveyendo una forma de tolerancia a ella. La argumentacion puede brindar la posibilidad de dar con ambos problemas. Primeramente, me-diante la construcción de un marco argumentativo o argumen-tation framework (AF) a partir de la KB inconsistente, pode-mos decidir si aceptar o rechazar una cierta conclusion o claim a través de la interacción entre argumentos y contra-argumentos. Segundo, mediante el manejo de la dinámica de argumentos del AF, podemos dar con la dinámica del conoci-miento de la KB inconsistente subyacente.Por un lado, propondremos una nueva familia de marcos argumentativos abstractos a los cuales referimos como generalizados, e identificamos como generalized abstract argumentation frameworks (GenAF), debido a su habilidad de adaptacion a diferentes lenguajes de representación. El objetivo es proveer un marco argumentativo, no completamente abstracto, para razonar por sobre las inconsistencias de KBs representadas a través de cualquier lenguaje que se sepa conforme algún fragmento de primer-orden. Las semánticas estándar de Dung son adaptadas para construir la maquinaria de razonamiento del GenAF. En lo que constituye un primer enfoque a revision de creencias en esta tesis, se propondrá un operador de debugging para la KB subyacente definido sobre las semán-ticas argumentativas para GenAFs como un tipo de consoli-dación: operación propuesta por Hansson para restaurar consistencia a KBs. Por ello, nos basaremos sobre sus postula-dos usuales para caracterizar axiomaticamente la operación de debugging propuesta, mostrando el correspondiente teorema de representación. Luego, proponemos la reificación del lenguaje abstracto para argumentos del GenAF al lenguaje básico de descripción ALC. Esto muestra la flexibilidad del formalismo presentado y una forma de aplicar argumentación a ontologías para razonar sobre las inconsistencias. Finalmen-te, la operación de debugging provee una herramienta para reparar inconsistencias y conceptos insatisfacibles, restau-rando consistencia-coherencia a las ontologías ALC. La dinámica de argumentos ha recientemente atraído atención y aunque algunos enfoques han sido propuestos, una axioma-tización completa dentro de la teoría de revisión de creen-cias constituyó un resultado pendiente hasta el momento. Una revision surge cuando deseamos que las semánticas argumentativas acepten un nuevo argumento. La teorıa del cambio argumentativo o Argument Theory Change (ATC) define operadores de revision que modifican un AF mediante el análisis de árboles de dialéctica argumentos como nodos y ataques como arcos como la semántica argumentativa adoptada. Presentaremos un simple enfoque a ATC basado en KBs proposicionales. Esto nos permite manejar el cambio de KBs inconsistentes basandonos en la teoría clásica de revi-sión de creencias, aunque al contrario de lo que ella indica, se evitará la restauración de consistencia de la KB a trabajar. Subsecuentemente, un conjunto de postulados de racionali-dad será adaptado a argumentación y finalmente, el modelo de cambio propuesto será relacionado a los postulados a través del correspondiente teorema de representación. Seguidamente, los resultados serán extendidos a description logics, para manejar el razonamiento y evolución ontológicos con tolerancia a inconsistencias. / Reasoning and change over inconsistent knowledge bases (KBs) is of utmost relevance in areas like medicine and law. Argumentation may bring the possibility to cope with both problems. Firstly, by constructing an argumentation frame-work (AF) from the inconsistent KB, we can decide whether to accept or reject a certain claim through the interplay among arguments and counterarguments. Secondly, by handling dynamics of arguments of the AF, we might deal with the dynamics of knowledge of the underlying inconsistent KB. On the one hand, we propose a new family of abstract argu-mentation frameworks which we refer as generalized (iden-tified through the acronym GenAF), due to its ability of adapting to different representation languages. The objective is to provide a not so, but still, abstract argumentation framework for reasoning over inconsistent knowledge bases (KBs) represented through any language known to conform to some first-order fragment. The well known Dungs standard semantics are adapted to construct the GenAFs reasoning machinery. Constituting the first approach to belief revision in this thesis work, we propose a debugging operator for the underlying KB defined upon the argumentation semantics for GenAFs, as a kind of belief revisions consolidation. A consolidation is a well known Hanssons operation for restoring consistency to KBs, therefore, we rely upon its usual postulates to axiomatically characterize the debugging operation proposed here, showing the corresponding representation theorem. Afterwards, we propose a reification of the GenAFs abstract language for arguments to the basic ALC description logic. This shows both the flexibility of the formalism presented, and a way to apply argumentation for reasoning over inconsistent ontologies, subject of utmost relevance in areas like medicine and law. Finally, the debugging operation provides a tool for debugging inconsistent ontologies and repairing unsatisfiable concepts, for restoring both consistency and coherency to ALC ontologies. Dynamics of arguments has recently attracted attention and although some approaches have been proposed, a full axiomatization within the theory of belief revision was still missing. A revision arises when we want the argumentation semantics to accept an argument. Argument Theory Change (ATC) encloses the revision operators that modify the AF by analyzing dialectical trees arguments as nodes and attacks as edges as the adopted argumentation semantics. We present a simple approach to ATC based on propositional KBs. This allows to manage change of incon-sistent KBs by relying upon classic belief revision, although contrary to it, consistency restoration of the KB is avoided. Subsequently, a set of rationality postulates adapted to argumentation is given, and finally, the proposed model of change is related to the postulates through the corresponding representation theorem. Afterwards, the results are extended to description logics, to handle ontology reasoning and evolution with tolerancy to inconsistency.

Description logics are knowledge representation and reasoning formalisms which represent conceptual knowledge on an abstract logical level. Concrete domains are a theoretically well-founded approach to the integration of description logic reasoning with reasoning about concrete objects such as numbers, time intervals or spatial regions. In this paper, the complexity of combined reasoning with description logcis and on concrete domains is investigated. We extend ALC(D), which is the basic description logic for reasoning with concrete domains, by the operators 'feature agreement' and 'feature disagreement'. For the extended logic,called ALCF(D), an algorithm for deciding the ABox consistency problem is devised. The strategy employed by this algorithm is vital for the efficient implementation of reasoners for description logics incorporating concrete domains. Based on the algorithm, it is proved that the standard reasoning problems for both logics ALC(D) and ALCF(D) are PSpace-complete - provided that the satisfiability test of the concrete domain used is in PSpace. / This is an extended version of the article in: Proceedings of IJCAI-99, Stockholm, Sweden, July 31-August 6, Morgan Kaufmann Publ. In ., San Mateo, CA, 1999

Number restrictions are concept constructors that are available in almost all implemented description logic systems. However, even though there has lately been considerable effort on integrating expressive role constructors into description logics, the roles that may occur in number restrictions are usually of a very restricted type. Until now, only languages with number restrictions on atomic roles and inversion of atomic roles, or with number restrictions on intersection of atomic roles have been investigated in detail. In the present paper, we increase the expressive power of description languages by allowing for more complex roles in number restrictions. As role constructors, we consider composition of roles (which will be present in all our languages), and intersection, union and inversion of roles in different combinations. We will present one decidability result (for the basic language that extends ALC by number restrictions on roles with composition), and three undecidability results for three different extensions of the basic language.

The problem of rewriting a concept given a terminology can informally be stated as follows: given a terminology T (i.e., a set of concept definitions) and a concept description C that does not contain concept names defined in T , can this description be rewritten into a 'related better' description E by using (some of) the names defined in T ? In this paper, we first introduce a general framework for the rewriting problem in description logics, and then concentrate on one specific instance of the framework, namely the minimal rewriting problem (where 'better' means shorter, and 'related' means equivalent). We investigate the complexity of the decision problem induced by the minimal rewriting problem for the languages FL0, ALN, ALE, and ALC, and then introduce an algorithm for computing (minimal) rewritings for the languages ALE and ALN. Finally, we sketch other interesting instances of the framework. Our interest for the minimal rewriting problem stems from the fact that algorithms for non-standard inferences, such as computing least common subsumers and matchers, usually produce concept descriptions not containing defined names. Consequently, these descriptions are rather large and hard to read and comprehend. First experiments in a chemical process engineering application show that rewriting can reduce the size of concept descriptions obtained as least common subsumers by almost two orders of magnitude. / Please download the revised version LTCS-00-04 containing revised proofs of the technical results. / An abridged version of this report appeared in the Proceedings of the International Conference on Knowledge Representation and Reasoning (KR'2000).

Recent research in the field of Description Logic (DL) investigated the complexity of the satisfiability problem for description logics that are obtained by enriching the well-known DL ALCQ with more complex set and cardinality constraints over role successors. The algorithms that have been proposed so far, despite providing worst-case optimal decision procedures for the concept satisfiability problem (both without and with a terminology) lack the efficiency needed to obtain usable implementations. In particular, the algorithm for the case without terminology is non-deterministic and the one for the case with a terminology is also best-case exponential. The goal of this thesis is to use well-established techniques from the field of numerical optimization, such as column generation, in order to obtain more practical algorithms. As a starting point, efficient approaches for dealing with counting quantifiers over unary predicates based on SAT-based column generation should be considered.:1. Introduction 2. Preliminaries 2.1. First-order logic 2.2. Linear Programming 2.3. The description logic ALCQ 2.4. Extending ALCQ with expressive role successor constraints 2.4.1. The logic QFBAPA 2.4.2 The description logic ALCSCC 3. The description logic ALCCQU 3.1. A normal form for ALCCQU 3.2. ALCQt as an equivalent formulation of ALCCQU 3.2.1. ALCQt is a sublogic of ALCCQU 3.2.2. ALCCQU is a sublogic of ALCQt 3.3. Model-theoretic characterization of ALCQt 3.3.1. ALCQt-bisimulation and invariance for ALCQt 3.3.2. Characterization of ALCQt concept descriptions 3.4. Expressive power 3.4.1. Relative expressivity of ALCQ and ALCCQU 3.4.2. Relative expressivity of ALCCQU and ALCSCC 3.5. ALCCQU as the first-order fragment of ALCSCC 4. Concept satisfiability in ALCCQU 4.1. The first-order fragment CQU 4.2. Column generation with SAT oracle 4.2.1. Column generation and CQU 4.2.2. From linear inequalities to propositional formulae 4.2.3. Column generation and ALCCQU 4.3. Branch-and-Price for ALCCQU concept satisfiability 4.4. Correctness of ALCCQU-BB 4.4.1. Complexity of ALCCQU-BB 5. Conclusion - Bibliography

The role-based paradigm has been introduced for the design of adaptive and context sensitive software systems. Naturally, a system built on top of the paradigm is expected to thrive in dynamic environments. In consequence, reasoning services over temporal aspect are essential in such a system. To represent context-dependent domains, various extensions of Description Logics (DLs) with context are introduced and studied. We focus on the family of Contextualized Description Logics (ConDLs) that have been shown capable to represent role-based modelling languages while retaining decidability. However, reasoning problems over dynamic settings under the logics are rather unexplored.