Terminological reasoning is inherently intractable

DOI10.1016/0004-3702(90)90087-GMaRDI QIDQ2638816zbMATH OpenOpenAlexFDO

Authors Bernhard Nebel

Publication date 1990

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(90)90087-g

zbMATH Keywords

terminological reasoningterminological representation languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30)

Recommendations

• scientific article; zbMATH DE number 1405451
• scientific article; zbMATH DE number 847979
• scientific article; zbMATH DE number 823628
• Justified terminological reasoning
• scientific article; zbMATH DE number 1292303
• scientific article; zbMATH DE number 5364052
• Syntactic analogies and impossible extensions
• Incompleteness results in Kripke semantics
• The logic of inexact concepts

Cites work

• scientific article; zbMATH DE number 4166932 (Why is no real title available?)
• scientific article; zbMATH DE number 67967 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A four-valued semantics for terminological logics
• An Efficient Unification Algorithm
• Computational complexity of terminological reasoning in BACK
• Linear unification

Cited in

(36)

• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• Pattern associativity and the retrieval of semantic networks
• Unification of concept terms in description logics
• The complexity of existential quantification in concept languages.
• Efficient TBox Reasoning with Value Restrictions using the wer Reasoner
• Reasoning within intuitionistic fuzzy rough description logics
• Extending the description logic \(\mathcal{EL}\) with threshold concepts induced by concept measures
• Description Logics
• The complexity of concept languages
• Using automata theory for characterizing the semantics of terminological cycles
• An empirical analysis of terminological representation systems
• The data complexity of the syllogistic fragments of English
• Attributive concept descriptions with complements
• Reasoning with ontologies
• Tractable reasoning via approximation
• Acquisition and validation of complex object database schemata supporting multiple inheritance
• ``Reducing classic to practice: Knowledge representation theory meets reality
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• Reasoning and query answering in description logics
• Reasoning within expressive fuzzy rough description logics
• The F-logic approach for description languages
• Debugging incoherent terminologies
• Human rationality challenges universal logic
• Computing the least common subsumer w.r.t. a background terminology
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• Planning from second principles
• The fuzzy description logic \(\mathsf{G}\)-\({\mathcal{FL}_0}\) with greatest fixed-point semantics
• PS\textsc{pace} tableau algorithms for acyclic modalized \({\mathcal{ALC}}\)
• An epistemic operator for description logics
• Consistency checking reduced to satisfiability of concepts in terminological systems
• Automata can show PSpace results for description logics
• Fuzzy description logics with general t-norms and datatypes
• Prototypes in a hybrid language with primitive descriptions
• Subsumption computed algebraically
• Complexity of Planning in Action Formalisms Based on Description Logics
• A refined architecture for terminological systems: Terminology = Schema + Views

This page was built for publication: Terminological reasoning is inherently intractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638816)