Terminological reasoning is inherently intractable

DOI10.1016/0004-3702(90)90087-GzbMath0717.68089MaRDI QIDQ2638816

Bernhard Nebel

Publication date: 1990

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

terminological reasoning; terminological representation languages

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T30: Knowledge representation

Related Items

Unification of concept terms in description logics, Attributive concept descriptions with complements, Automata can show PSpace results for description logics, A refined architecture for terminological systems: Terminology = Schema + Views, An epistemic operator for description logics, Subsumption computed algebraically, Prototypes in a hybrid language with primitive descriptions, Pattern associativity and the retrieval of semantic networks, Acquisition and validation of complex object database schemata supporting multiple inheritance, An empirical analysis of terminological representation systems, The complexity of concept languages, Consistency checking reduced to satisfiability of concepts in terminological systems, Using automata theory for characterizing the semantics of terminological cycles, Tractable reasoning via approximation, The F-logic approach for description languages, ``Reducing classic to practice: Knowledge representation theory meets reality, Computing the least common subsumer w.r.t. a background terminology, Debugging incoherent terminologies, Complexity of Planning in Action Formalisms Based on Description Logics

Cites Work

• Computational complexity of terminological reasoning in BACK
• A four-valued semantics for terminological logics
• Linear unification
• An Efficient Unification Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item