Practical Reasoning for Very Expressive Description Logics

By Ian Horrocks, U. Sattler, Stephan Tobies. Logic Journal of the IGPL, 2000

426 citations recorded by the source corpus.

Description Logics (DLs) are a family of knowledge representation formalisms mainly characterised by constructors to build complex concepts and roles from atomic ones. Expressive role constructors are important in many applications, but can be computationally problematical. We present an algorithm that decides satisfiability of the DL ALC extended with transitive and inverse roles and functional restrictions with respect to general concept inclusion axioms and role hierarchies; early experiments indicate that this algorithm is well-suited for implementation. Additionally, we show that ALC extended with just transitive and inverse roles is still in PSPACE. We investigate the limits of decidability for this family of DLs, showing that relaxing the constraints placed on the kinds of roles used in number restrictions leads to the undecidability of all inference problems. Finally, we describe a number of optimisation techniques that are crucial in obtaining implementations of the decision procedures, which, despite the worst-case complexity of the problem, exhibit good performance with real-life problems.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/739963f59ea9ccd1ae7e8e7fc8bbadc1e8ee2036

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Consistent Evolution of OWL Ontologies (2005, background): “1 For the direct model-theoretic semantics of SHOIN (D) we refer the reader to [9].”
A data-oriented survey of context models (2007, background): “However, most of the interesting ontologies found on the Web are at least as expressive as OWL-Lite (SHIF), where, for instance, just concept sati.ability is EXPTime-complete [29]. related information makes it di.cult to deeply understand the requirements that have to be considered when proposin”
Computing the Least Common Subsumer w.r.t. a Background Terminology (2004, methodology): “In particular, the W3C recommended ontology web language OWL [39] is based on an expressive description logic [40,41].”
Hypertableau Reasoning for Description Logics (2009, background): “Horrocks et al. (2000b) do not physically remove successors, but mark them as “not present” by setting the relevant edge labels to ∅.”
Pellet: A practical OWL-DL reasoner (2007, background): “Several blocking strategies have been developed for different expressivities (see, for example, [15]).”
OWL 2: The next step for OWL (2008, neutral): “Furthermore, the free usage of vocabulary adds an additional source of undecidability; for example, OWL 1 Full does not enforce the well-known restrictions needed for decidability, such as using only simple roles in number restrictions [20].”
Complexity results and practical algorithms for logics in knowledge representation (2001, background): “While for ALC, or, more precisely, for its syntactic variant K, PSpace-completeness has already been established quite some time ago by Ladner (1977), the situation is entirely different for ALCQ or its corresponding (multi)modal logic Gr(KR).”
The DL-Lite Family and Relations (2009, background): “We remind the reader of the standard restriction limiting the use of transitive roles in DLs (see, e.g., Horrocks, Sattler, & Tobies, 2000 ): namely, only simple roles R are allowed in concepts of the form q R, for q 2, where by a simple role in a given TBox T we understand a role without transitiv”
From SHIQ and RDF to OWL: the making of a Web Ontology Language (2003, methodology): “A suitable balance between these computational requirements and the expressive requirements identiﬁed in [17] was achieved by basing the design of OWL on the SH family of Description Logics [24].”