Note: Cover -- Half-title -- Title -- Copyright -- Contents -- Contributors -- Preface -- 1 An Introduction to Description Logics -- Abstract -- 1.1 Introduction -- 1.2 From networks to Description Logics -- 1.2.1 Network-based representation structures -- 1.2.2 A logical account of network-based representation structures -- 1.2.3 Reasoning -- 1.3 Knowledge representation in Description Logics -- 1.3.1 The TBox -- 1.3.2 The ABox -- 1.4 From theory to practice: Description Logic systems -- 1.4.1 The design of knowledge representation systems based on Description Logics -- 1.4.2 Knowledge representation systems based on Description Logics -- 1.4.2.1 Pre-Description Logic systems -- 1.4.2.2 Description Logic systems -- 1.4.2.3 Current generation Description Logic systems -- 1.5 Applications developed with Description Logic systems -- 1.5.1 Modeling with Description Logics -- 1.5.2 Application domains -- 1.5.2.1 Software engineering -- 1.5.2.2 Configuration -- 1.5.2.3 Medicine -- 1.5.2.4 Digital libraries and Web-based information systems -- 1.5.2.5 Other application domains -- 1.5.3 Application areas -- 1.5.3.1 Natural language -- 1.5.3.2 Database management -- 1.6 Extensions of Description Logics -- 1.6.1 Language extensions -- 1.6.1.1 Non-monotonic reasoning -- 1.6.1.2 Modal representation of knowledge and belief -- 1.6.1.3 Epistemic reasoning -- 1.6.1.4 Temporal reasoning -- 1.6.1.5 Representation of uncertain and vague knowledge -- 1.6.1.6 Concrete domains -- 1.6.2 Additional reasoning services -- 1.6.2.1 Least common subsumer and most specific concept -- 1.6.2.2 Unification and matching -- 1.6.2.3 Concept rewriting -- 1.7 Relationship to other fields of Computer Science -- 1.7.1 Description Logics and other class-based formalisms -- 1.7.2 Relationships to other logics -- 1.8 Conclusion -- Acknowledgements -- Part I Theory. , 2 Basic Description Logics -- Abstract -- 2.1 Introduction -- 2.2 Definition of the basic formalism -- 2.2.1 Description languages -- 2.2.1.1 The basic description language AL -- 2.2.1.2 The family of AL-languages -- 2.2.1.3 Description languages as fragments of predicate logic -- 2.2.2 Terminologies -- 2.2.2.1 Terminological axioms -- 2.2.2.2 Definitions -- 2.2.2.3 Fixpoint semantics for terminological cycles -- 2.2.2.4 Existence of fixpoint models -- 2.2.2.5 Terminologies with inclusion axioms -- 2.2.3 World descriptions -- 2.2.3.1 Assertions about individuals -- 2.2.3.2 Individual names in the description language -- 2.2.4 Inferences -- 2.2.4.1 Reasoning tasks for concepts -- 2.2.4.2 Eliminating the TBox -- 2.2.4.3 Reasoning tasks for ABoxes -- 2.2.4.4 Closed-vs.open-world semantics -- 2.2.5 Rules -- 2.3 Reasoning algorithms -- 2.3.1 Structural subsumption algorithms -- 2.3.2 Tableau algorithms -- 2.3.2.1 A tableau-based satisfiability algorithm for ALCN -- 2.3.2.2 Complexity issues -- 2.3.2.3 Extension to the consistency problem for ABoxes -- 2.3.2.4 Extension to general inclusion axioms -- 2.3.2.5 Extension to other language constructors -- 2.3.3 Reasoning w.r.t. terminologies -- 2.3.3.1 Acyclic terminologies -- 2.3.3.2 Cyclic terminologies -- 2.4 Language extensions -- 2.4.1 Role constructors -- 2.4.2 Expressive number restrictions -- 2.4.3 Role-value-maps -- Acknowledgement -- 3 Complexity of Reasoning -- Abstract -- 3.1 Introduction -- 3.1.1 Intuition: sources of complexity -- 3.1.1.1 OR-branching -- 3.1.1.2 AND-branching -- 3.1.2 Overview of the chapter -- 3.2 OR-branching: finding a model -- 3.2.1 Intractability in FL -- 3.2.2 Intractability in FL plus qualified existential quantification and number restrictions -- 3.2.2.1 Simulating R.C with role conjunction -- 3.3 AND-branching: finding a clash. , 3.3.1 Intractability of satisfiability in ALE -- 3.3.2 FL plus role conjunction and role inverse -- 3.3.3 FL plus role conjunction and role chain -- 3.3.4 FL plus role chain and role inverse -- 3.3.4.1 Simulating R.C via role chains and role inverses -- 3.4 Combining sources of complexity -- 3.4.1 PSpace -hardness of satisfiability in ALC -- 3.4.2 A remark on reductions -- 3.5 Reasoning in the presence of axioms -- 3.5.1 Results from Propositional Dynamic Logic -- 3.5.2 Axioms and succinct representations of AND-OR graphs -- 3.5.3 Syntax restrictions on axioms -- 3.6 Undecidability -- 3.6.1 Undecidability of role-value-maps -- 3.7 Reasoning about individuals in ABoxes -- 3.8 Discussion -- 3.9 A list of complexity results for subsumption and satisfiability -- 3.9.1 Notation -- 3.9.2 Subsumption in PTime -- 3.9.3 NP and CONP -- 3.9.4 PSPACE -- 3.9.5 EXPTIME -- 3.9.6 NEXPTIME -- 3.9.7 Undecidability results -- Acknowledgements -- 4 Relationships with other Formalisms -- Abstract -- 4.1 AI knowledge representation formalisms -- 4.1.1 Semantic networks -- 4.1.2 Frame systems -- 4.1.3 Conceptual graphs -- Simple conceptual graphs -- Concept descriptions and simple graphs -- 4.2 Logical formalisms -- 4.2.1 Restricted variable fragments -- 4.2.2 Modal logics -- 4.2.3 Guarded fragments -- 4.3 Database models -- 4.3.1 Semantic data models -- 4.3.1.1 Formalization -- 4.3.1.2 Correspondence with Description Logics -- 4.3.1.3 Applications of the correspondence -- 4.3.2 Object-oriented data models -- 4.3.2.1 Formalization -- 4.3.2.2 Correspondence with Description Logics -- 4.3.2.3 Applications of the correspondence -- 4.3.3 Semistructured data models and XML -- 4.3.3.1 Relationship between semistructured data and Description Logics -- 4.3.3.2 Relationship between XML and Description Logics -- 5 Expressive Description Logics -- Abstract -- 5.1 Introduction. , 5.2 Correspondence between Description Logics and Propositional Dynamic Logics -- 5.2.1 Description Logics -- 5.2.2 Propositional Dynamic Logics -- 5.2.3 The correspondence -- 5.3 Functional restrictions -- 5.3.1 Automata on infinite trees -- 5.3.2 Reasoning in ALCFI -- 5.4 Qualified number restrictions -- 5.4.1 Reification of roles -- 5.4.2 Reducing ALCQI to ALCFI -- 5.5 Objects -- 5.6 Fixpoint constructs -- 5.7 Relations of arbitrary arity -- 5.7.1 Boolean constructs on roles and role inclusion axioms -- 5.7.2 Structured objects -- 5.8 Finite model reasoning -- 5.8.1 Finite model reasoning using linear inequalities -- 5.8.2 Finite model reasoning in expressive Description Logics -- 5.9 Undecidability results -- 5.9.1 Boolean constructs on complex roles -- 5.9.2 Role-value-maps -- 5.9.3 Number restrictions on complex roles -- 6 Extensions to Description Logics -- Abstract -- 6.1 Introduction -- 6.2 Language extensions -- 6.2.1 Concrete domains -- 6.2.1.1 The family of Description Logics ALC(D) -- 6.2.1.2 Predicate restrictions on role chains -- 6.2.1.3 Predicate restrictions defining roles -- 6.2.2 Modal extensions -- 6.2.3 Epistemic operators -- 6.2.3.1 ALCK as a query language -- 6.2.3.2 Semantics for procedural rules -- 6.2.3.3 An extension of ALCK -- 6.2.4 Temporal extensions -- 6.2.5 Representing uncertain and vague knowledge -- 6.2.5.1 Probabilistic extensions -- 6.2.5.2 Fuzzy extensions -- 6.2.6 Extensions by default rules -- 6.3 Non-standard inference problems -- 6.3.1 Techniques for solving non-standard inferences - a general remark -- 6.3.2 Least common subsumer and most specific concept -- 6.3.2.1 Computing the lcs and the msc -- 6.3.3 Unification and matching -- 6.3.3.1 Unification -- 6.3.3.2 Matching -- 6.3.3.3 Results on matching and unification -- 6.3.4 Concept rewriting -- Acknowledgement -- Part II Implementation. , 7 From Description Logic Provers to Knowledge Representation Systems -- Abstract -- 7.1 Introduction -- 7.2 Basic access -- 7.3 Advanced application access -- 7.3.1 Efficiency -- 7.3.2 Wide application programming interface -- 7.3.3 Remote and concurrent access -- 7.3.4 Platforms -- 7.4 Advanced human access -- 7.4.1 Explanation -- 7.4.2 Error handling -- 7.4.3 Pruning -- 7.4.4 Knowledge acquisition -- 7.5 Other technical concerns -- 7.6 Public relations concerns -- 7.7 Summary -- 8 Description Logic Systems -- Abstract -- 8.1 New light through old windows? -- 8.2 The first generation -- KL-ONE -- KRYPTON -- NIKL, PENNI, KL-TWO -- KANDOR -- 8.3 Second generation Description Logic systems -- CLASSIC -- LOOM -- BACK and FLEX -- KRIS -- CRACK -- Other systems -- Summary: standard inference services of Description Logics systems -- 8.4 The next generation: Fact, DLP and RACER -- FaCT -- DLP -- RACER -- 8.5 Lessons learned -- 9 Implementation and Optimization Techniques -- Abstract -- 9.1 Introduction -- 9.1.1 Performance analysis -- 9.2 Preliminaries -- 9.2.1 Syntax and semantics -- 9.2.2 Reasoning services -- 9.2.3 Unfolding -- 9.2.4 Internalization -- 9.3 Subsumption-testing algorithms -- 9.3.1 Structural subsumption algorithms -- 9.3.2 Logical algorithms -- 9.3.2.1 Tableau algorithms -- 9.4 Theory versus practice -- 9.4.1 Worst-case complexity -- 9.4.2 Typical-case complexity -- 9.4.3 Reasoning with a knowledge base -- 9.5 Optimization techniques -- 9.5.1 Pre-processing optimizations -- 9.5.1.1 Normalization -- 9.5.1.2 Absorption -- 9.5.2 Optimizing classification -- 9.5.3 Optimizing subsumption testing -- 9.5.4 Optimizing satisfiability testing -- 9.5.4.1 Semantic branching search -- 9.5.4.2 Local simplification -- 9.5.4.3 Dependency directed backtracking -- 9.5.4.4 Heuristic guided search -- 9.5.4.5 Caching satisfiability status -- 9.6 Discussion. , Part III Applications.