Computational complexity of terminological reasoning in BACK

doi:10.1016/0004-3702(88)90066-5

Artificial Intelligence

Volume 34, Issue 3, April 1988, Pages 371-383

https://doi.org/10.1016/0004-3702(88)90066-5 Get rights and content

Abstract

Terminological reasoning is a mode of reasoning all hybrid knowledge representation systems based on KL-ONE rely on. After a short introduction of what terminological reasoning amounts to, it is proven that a complete inference algorithm for the BACK system would be computationally intractable. Interestingly, this result also applies to the KANDOR system, which had been conjectured to realize complete terminological inferences with a tractable algorithm. More generally, together with an earlier paper of Brachman and Levesque it shows that terminological reasoning is intractable for any system using a nontrivial description language. Finally, consequences of this distressing result are briefly discussed.

References (21)

R.J. Brachman
On the epistomological status of semantic networks
R.J. Brachman et al.
An overview of the KL-ONE knowledge representation system
Cognitive Sci.
(1985)
T. Lipkis
A KL-ONE classifier
P.F. Patel-Schneider
Small can be beautiful in knowledge representation
J.F. Allen
Maintaining knowledge about temporal intervals
Commun. ACM
(1983)
R.J. Brachman et al.
The tractability of subsumption in frame-based description languages
R.J. Brachman et al.
An essential hybrid reasoning system: Knowledge and symbol level accounts in KRYPTON
R.J. Brachman et al.
KRYPTON: A functional approach to knowledge representation
IEEE Computer
(1983)
J. Edelmann et al.
Data models in knowledge representation systems: A case study
M.R. Garey et al.
Computers and Intractability—A Guide to the Theory of NP-Completeness
(1979)

There are more references available in the full text version of this article.

Cited by (91)

Reasoning within extended fuzzy description logic
2009, Knowledge-Based Systems
An extended fuzzy description logic is proposed to increase expressive power for complex fuzzy information. We introduce cut sets of the fuzzy concepts and fuzzy roles as atomic concepts and atomic roles, and inherit concept constructors of the description logics to support a new logic system for fuzzy knowledge representation. We define the syntax, semantics and knowledge base of the extended fuzzy description logic, and focus on sat-domain and consistency as main reasoning tasks. We also present sound and complete tableau algorithms for these reasoning tasks, and prove the complexity of them is PSPACE-complete. Compared with the other fuzzy description logics, the extended fuzzy description logic can express more wide fuzzy information.
13 Description logic
2007, Studies in Logic and Practical Reasoning
Modal logic is an intrinsically intensional logic, suitable only for applications such as reasoning about necessity, possibility, and knowledge. Description logics are undeniably modal logics but are extremely well suited for reasoning about ordinary individuals and the relations between them. The basic components of description logics are concept languages, terminological formalisms, and assertional formalisms. The concept language ALC is only one member of a large family of concept languages. The chapter introduces syntax and semantics of the basic description logics (DL) ALC, and shows its relationship to multi-modal K. It then discusses additional DL constructors and describes their modal logics (ML) counterparts. In addition to these constructors, DLs provide their users with a terminological formalism, which allows introducing names for complex concepts, and an assertional formalism, which allows stating facts about specific individuals/objects. The known complexity results for DLs and structural subsumption algorithms for some of them are described. The bi-simulation characterizations of the corresponding ML fragments are also considered. Some non-standard inferences in DLs and means of expressiveness that do not have immediate ML counterparts are introduced.
DFL - A dialog based integration of concept and rule reasoners
2001, Data and Knowledge Engineering
Citation Excerpt :
Constraint-based algorithms can handle cyclic terminological definitions and are complete. Major efforts were devoted to the study of the subsumption problem in different DLs [28,41,49,50,54], to the study of subsumption/classification algorithms in existing systems [8,47], and to the development of subsumption algorithms [35,52,55]. These research efforts show that in expressive DLs subsumption is not tractable.
Description logics (DLs) are subsets of first-order logic (FOL), designed for reasoning about class-based knowledge. Their expressive power is deliberately restricted, so as to enable efficient inference. A DL reasoner or knowledge base is intended to be embedded as a special purpose component in a heterogeneous knowledge base. Therefore, the development of integration frameworks of DLs and other forms of reasoning is essentially important. In this paper, we introduce a formal scheme for the integration of information sources for which a combined declarative semantics is not available. The integration is defined by a syntactic compositional semantics, and implemented by a dialog process in which the independent reasoners make their failures public. This scheme is used to formalize the integration of a DL reasoner with an expressive rule reasoner (for which a combined declarative semantics is not known). It is implemented in the $DFL$ system, that integrates a DL reasoner and an F-Logic rule reasoner. The integrated system gives rise to a rich dialog between its components, since the DL inferences can trigger new rule inferences, and rule inferences can trigger new DL inferences. The $DFL$ system is the first to support a true dialog between a DL and a rule reasoners, that operate under different semantical policies, e.g., the open world assumption (OWA) for the DL reasoner, and the closed world assumption (CWA) for the rule reasoner. This architecture generalizes all existing hybrids of descriptions and rules.
Unification of Concept Terms in Description Logics
2001, Journal of Symbolic Computation
EXPTIME tableaux for ALC
2000, Artificial Intelligence
The last years have seen two major advances in Knowledge Representation and Reasoning. First, many interesting problems (ranging from Semi-structured Data to Linguistics) were shown to be expressible in logics whose main deductive problems are EXPtime-complete. Second, experiments in automated reasoning have substantially broadened the meaning of “practical tractability”. Instances of realistic size for Pspace-complete problems are now within reach for implemented systems.
Still, there is a gap between the reasoning services needed by the expressive logics mentioned above and those provided by the current systems. Indeed, the algorithms based on tree-automata, which are used to prove EXPtime-completeness, require exponential time and space even in simple cases. On the other hand, current algorithms based on tableau methods can take advantage of such cases, but require double exponential time in the worst case.
We propose a tableau calculus for the description logic $ALC$ for checking the satisfiability of a concept with respect to a TBox with general axioms, and transform it into the first simple tableau-based decision procedure working in single exponential time.
To guarantee the ease of implementation, we also discuss the effects that optimizations (propositional backjumping, simplification, semantic branching, etc.) might have on our complexity result, and introduce a few optimizations ourselves.
Inheritance hierarchy design in object-oriented databases
1999, Data and Knowledge Engineering
Object-oriented database schema design is still mostly an art. One of the difficulties encountered during design is typing conflicts induced by multiple inheritance. In this paper, we propose a method for treating such a kind of conflicts. Our approach to inheritance conflict solving consists of several ingredients. First, we rely on branding, to introduce ‘type equivalence by name’, thus allowing a designer to distinguish between structurally similar but se-mantically different types. However, we offer a heuristic that does not require a designer to explicitly state branding declarations. Second, we describe various kinds of conflicts, and we offer a set of procedures that analyze a schema to discover such conflicts, classify them, offering potential solutions, if possible. The procedures have been conceived for a design system that allows a designer maximum flexibility, while guiding him/her to a correct design.

View all citing articles on Scopus

^☆: This work was partially supported by the EEC and is part of ESPRIT project 311, which involves the following participants: Nixdorf, Olivetti, Bull, Technische Universität Berlin, Universita di Bologna, Universität Hildesheim and Universita di Torino.

View full text

Research noteComputational complexity of terminological reasoning in BACK☆

Abstract

Cognitive Sci.

Maintaining knowledge about temporal intervals

Commun. ACM

The tractability of subsumption in frame-based description languages

An essential hybrid reasoning system: Knowledge and symbol level accounts in KRYPTON

KRYPTON: A functional approach to knowledge representation

IEEE Computer

Data models in knowledge representation systems: A case study

Computers and Intractability—A Guide to the Theory of NP-Completeness

Research note
Computational complexity of terminological reasoning in BACK☆