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

• A four-valued semantics for terminological logics
• An Efficient Unification Algorithm
• Computational complexity of terminological reasoning in BACK
• 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?)
• Linear unification

Cited in

(36)

• Fuzzy description logics with general t-norms and datatypes
• Reasoning within expressive fuzzy rough 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
• Human rationality challenges universal logic
• ``Reducing classic to practice: Knowledge representation theory meets reality
• Computing the least common subsumer w.r.t. a background terminology
• Reasoning within intuitionistic fuzzy rough description logics
• Debugging incoherent terminologies
• Planning from second principles
• The fuzzy description logic \(\mathsf{G}\)-\({\mathcal{FL}_0}\) with greatest fixed-point semantics
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• Complexity of Planning in Action Formalisms Based on Description Logics
• PS\textsc{pace} tableau algorithms for acyclic modalized \({\mathcal{ALC}}\)
• Description Logics
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• scientific article; zbMATH DE number 67503 (Why is no real title available?)
• Reasoning and query answering in description logics
• The data complexity of the syllogistic fragments of English
• Unification of concept terms in description logics
• Efficient TBox Reasoning with Value Restrictions using the wer Reasoner
• Extending the description logic \(\mathcal{EL}\) with threshold concepts induced by concept measures
• Reasoning with ontologies
• Attributive concept descriptions with complements
• Automata can show PSpace results for description logics
• The complexity of existential quantification in concept languages.

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)