A tableaux decision procedure for SHOIQ
Research Explorer (The University of Manchester)Published 30 July 2005
Ian Horrocks, Ulrike Sattler
Citations367
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper presents a tableaux decision procedure for SHOIQ, the DL underlying OWL DL, and to the best of the knowledge, this is the first goal-directed decision procedure to be presented.
Abstract
OWL DL, a new W3C ontology language recommendation, is based on the expressive description logic SHOIN. Although the ontology consistency problem for SHOIN is known to be decidable, up to now there has been no known “practical ” decision procedure, i.e., a goal directed procedure that is likely to perform well with realistic ontology derived problems. We present such a decision procedure (for SHOIQ, a slightly more expressive logic than SHOIN), extending the well known algorithm for SHIQ,
Keywords
Computer Science
Cambridge University Press eBooksThe Description Logic Handbook
6,212 Citations2007Franz Baader, Franz Baader +17 more
Journal of Web SemanticsPellet: A practical OWL-DL reasoner
2,585 Citations2007Evren Sirin, Bijan Parsia +3 more
Pellet is the first sound and complete OWL-DL reasoner with extensive support for reasoning with individuals, user-defined datatypes, and debugging support for ontologies.
Data Archiving and Networked Services (DANS)OWL Web Ontology Language - Reference
2,387 Citations2004Mike Dean, A.T. Schreiber +7 more
This document contains a structured informal description of the full set of {owL} language constructs and is meant to serve as a reference for {OWL} users who want to construct {OWl} ontologies.
Journal of Web SemanticsFrom SHIQ and RDF to OWL: the making of a Web Ontology Language
1,449 Citations2003Ian Horrocks, Peter F. Patel‐Schneider +1 more
This paper discusses how the philosophy and features of OWL can be traced back to these older formalisms, with modifications driven by several other constraints on OWL.
Journal of Computer and System SciencesPropositional dynamic logic of regular programs
1,191 Citations1979Michael J. Fischer, Richard E. Ladner
A formal syntax and semantics for the propositional dynamic logic of regular programs is defined and principal conclusions are that deciding satisfiability of length n formulas requires time d n /log n for some d > 1, and that satisfiability can be decided in nondeterministic time cn for some c.
Lecture notes in computer scienceRACER System Description
903 Citations2001Volker Haarslev, Ralf Möller
RACER implements a TBox and ABox reasoner for the logic SHIQ, the first full-fledged ABox description logic system for a very expressive logic and is based on optimized sound and complete algorithms.
Lecture notes in computer scienceFaCT++ Description Logic Reasoner: System Description
782 Citations2006Dmitry Tsarkov, Ian Horrocks
This is a system description of the Description Logic reasoner FaCT++, which implements a tableaux decision procedure for the well known $\mathcal{SHOIQ}$ description logic, with additional support for datatypes, including strings and integers.
Lecture notes in computer sciencePractical Reasoning for Expressive Description Logics
534 Citations1999Ian Horrocks, Ulrike Sattler +1 more
An algorithm is presented that decides satisfiability of the DL ACC extended with transitive eind inverse roles, role hierarchies, and quaJifying number restrictions, and early experiments indicate that this algorithm is well-suited for implementation.
A correspondence theory for terminological logics: preliminary report
466 Citations1991Klaus Schild
It is proved that universal implications can be expressed within TSC, and it is shown that features correspond to deterministic programs in dynamic logic preserves decidability, although violates its finite model property.
Elsevier eBooksLIVING WITH CLASSIC
400 Citations1991Ronald J. Brachman, Deborah L. McGuinness +3 more
By analyzing the representational strengths and weaknesses of CLASSIC, this work considers the circumstances under which it is most appropriate to use (or not use) it and addresses some of the key difficult issues encountered by new users.
Studia LogicaAn Overview of Tableau Algorithms for Description Logics
388 Citations2001Franz Baader, Ulrike Sattler
This article focuses on three features that play an important rôle in description logics (number restrictions, terminological axioms, and role constructors), and shows how they can be taken into account by tableau algorithms.
arXiv (Cornell University)Complexity Results and Practical Algorithms for Logics in Knowledge Representation
337 Citations2001Stephan Tobies
A number of novel complexity results and practical algorithms for expressive DLs that provide different forms of counting quantifiers are established and it is shown that, in many cases, adding local counting in the form of qualifying number restrictions to DLs does not increase the complexity of the inference problems, even if binary coding of numbers in the input is assumed.
SciDok (Saarland University and State Library)A scheme for integrating concrete domains into concept languages
316 Citations1991Franz Baader, Philipp Hanschke
This paper shall define a terminological and an assertional language, and consider the important inference problems such as subsumption, instantiation, and consistency, and proposes a scheme for integrating such concrete domains into concept languages.
Ontology reasoning in the SHOQ(D) description logic
313 Citations2001Ian Horrocks, Ulrike Sattler
SHOQ(D) is an expressive description logic equipped with named individuals and concrete datatypes which has almost exactly the same expressive power as the latest web ontology languages (e.g., OIL and DAML).
Description logic framework for information integration
244 Citations1998Diego Calvanese, Giuseppe De Giacomo +3 more
Research Explorer (The University of Manchester)Reasoning with Individuals for the Description Logic SHIQ
233 Citations2000Ian Horrocks, Ulrike Sattler +1 more
SciDok (Saarland University and State Library)Decidable reasoning in terminological knowledge representation systems
190 Citations1993Martin Buchheit, Francesco M. Donini +1 more
The decidability of a number of desirable TKRS-deduction services are proved through a sound, complete and terminating calculus for reasoning in ALCNR-knowledge bases, and the result that inclusion statements in A LCNR can be simulated by terminological cycles, if descriptive semantics is adopted.
arXiv (Cornell University)Reasoning with Individuals for the Description Logic SHIQ
166 Citations2000Ian Horrock, Ulrike Sattler +1 more
SciDok (Saarland University and State Library)Qualifying number restrictions in concept languages
165 Citations1991Bernhard Hollunder, Franz Baader
This paper presents a subsumption algorithm for this language, which is sound and complete, and discusses why the subsumption problem in this language is rather hard from a computational point of view, which leads to an idea of how to recognize concepts which cause tractable problems.
The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics
163 Citations2000Stephan Tobies
Journal of Logic and ComputationOptimizing description logic subsumption
163 Citations1999Ian Horrocks
Effective optimization techniques can make a dramatic difference in the performance of knowledge representation systems based on expressive description logics and difficult problems in propositional modal logic can be effectively solved using the same techniques.
TBox and ABox Reasoning in Expressive Description Logics.
162 Citations1996Giuseppe De Giacomo, Maurizio Lenzerini
Lecture notes in computer scienceA terminological knowledge representation system with complete inference algorithms
140 Citations1991Franz Baader, Bernhard Hollunder
The formal model-theoretic semantics which has been introduced for kl-one languages [BL84] provides means for investigating soundness and completeness of inference algorithms.
Boosting the correspondence between description logics and propositional dynamic logics
124 Citations1994Giuseppe De Giacomo, Maurizio Lenzerini
This paper derives decidability and complexity results for some of the most expressive logics appeared in the literature, and from the standpoint of PDLs, derives a general methodology for the representation of several forms of program determinism and for the specification of partial computations.
Data & Knowledge EngineeringReasoning with individuals in concept languages
106 Citations1994Andrea Schaerf
The consequences of introducing a constructor for building a concept from a set of enumerated individuals in the concept description language are investigated and some complexity results are provided on it.
IEEE Intelligent Systems and their ApplicationsAn industrial-strength description logic-based configurator platform
95 Citations1998Deborah L. McGuinness, James R. Wright
The Prose configurators are based on CLASSIC, a description logic-based knowledge representation system, which is less expressive than many description logic systems, but it has been widely used in both industrial applications and academic systems.
Complexity of two-variable logic with counting
90 Citations2002Leszek Pacholski, Wiesław Szwast +1 more
It is proved that the problem of satisfiability of sentences of C/sub 1//sup 2/ is NEXPTIME-complete, which easily implies that the satisfiability problem for C/sup2/ is in non-deterministic, doubly exponential time.
Lecture notes in computer scienceFramework for an Automated Comparison of Description Logic Reasoners
65 Citations2006Tom Gardiner, Dmitry Tsarkov +1 more
This paper presents a system that allows users to test and compare OWL reasoners using an extensible library of real-life ontologies and to check the “correctness” of the reasoners by comparing the computed class hierarchy.
Efficient reasoning with range and domain constraints
64 Citations2004Dmitry Tsarkov, Ian Horrocks
This work shows how a tableaux algorithm for SHIQ can be extended to support role boxes that include range and domain axioms, and proves that the extended algorithm is still a decision procedure for the satisfiability and subsumption of SHIQ concepts w.r.t. such a role box.
AI MagazineTerm Subsumption Languages in Knowledge Representation
56 Citations1990Peter F. Patel‐Schneider, Bernd Owsnicki-Klewe +8 more
The Workshop on Term Subsumption Languages in Knowledge Representation was held 18-20 October 1989 at the Inn at Thorn Hill, located in the White Mountain region of New Hampshire.
Oxford University Research Archive (ORA) (University of Oxford)From wine to water: optimizing description logic reasoning for nominals
53 Citations2006Evren Sirin, Bernardo Cuenca Grau +1 more
New techniques for optimizing DL reasoning in the presence of nominals in the TBox and individuals in a large ABox are presented and found that they suffice for efficiently classifying the famous Wine Ontology.
Lecture notes in computer scienceThe Description Logic ALCNH R + Extended with Concrete Domains: A Practically Motivated Approach
49 Citations2001Volker Haarslev, Ralf Möller +1 more
The description logic ALCNHR+(D)- is introduced and it is shown that the results can be exploited for building practical description logic systems for solving e.g. configuration problems.
Lecture notes in computer scienceFaCT and DLP
41 Citations1998Ian Horrocks, Peter F. Patel‐Schneider
Tests were performed on a description logic classifier whose description language is a superset of K4(m) and whose subsumption reasoning uses a sound and complete tableaux algorithm, FaCT, which employs a wide range of optimisations.
International Joint Conference on Artificial IntelligenceOrdering heuristics for description logic reasoning
35 Citations2005Dmitry Tsarkov, Ian Horrocks
A new architecture for Description Logic implementations is presented, a range of new optimisation techniques and an empirical analysis of their effectiveness are presented.
Implementing and Testing Expressive Description Logics: a Preliminary Report
33 Citations1995Paolo Bresciani, Enrico Franconi +1 more
The aim of the crack project is the research and the development of a knowledge representation architecture based on description logics, characterized by an order parameter generating phase transitions in the satis ability probability space.
Lecture notes in computer scienceWeb Ontology Reasoning with Datatype Groups
33 Citations2003Jeff Z. Pan, Ian Horrocks
This paper presents a new approach, the datatype group approach, to integrating DLs with multiple datatypes, and discusses the advantages of such approach over the existing ones and shows how a tableaux algorithm for the description logic SHOQ(Dn) can be modified in order to reason withdatatype groups.
Tableau Systems for SHIO and SHIQ.
15 Citations2004Jan Hladík, Jörg Model
Tableau systems for two expressive DLs, the new DL SHIO and the wellknown SHIQ, are presented, obtaining that SHIO satisfiability is ExpTime-complete and can be decided by a tableau algorithm and the succinctness of the proofs demonstrates how the framework simplifies the design of TAs.
AI CommunicationsUsing Terminological Reasoning in Hybrid Systems
6 Citations1990Francesco M. Donini, Maurizio Lenzerini +1 more