The complexity of existential quantification in concept languages.

DOI10.1016/0004-3702(92)90076-AMaRDI QIDQ989170zbMATH OpenOpenAlexWikidataFDO

Authors F. M. Donini, Maurizio Lenzerini, Daniele Nardi, Bernhard Hollunder, Werner Nutt, Alberto Marchetti-Spaccamela

Publication date 27 August 2010

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(92)90076-a

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30) Logic in artificial intelligence (68T27)

Recommendations

• scientific article; zbMATH DE number 140381
• The complexity of concept languages
• scientific article; zbMATH DE number 2160560
• scientific article; zbMATH DE number 3981154
• Quantifiers and cognition: logical and computational perspectives
• scientific article; zbMATH DE number 4058877
• scientific article; zbMATH DE number 1342272
• Publication:4508560

Cites work

• scientific article; zbMATH DE number 67967 (Why is no real title available?)
• scientific article; zbMATH DE number 140381 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3274715 (Why is no real title available?)
• Attributive concept descriptions with complements
• Computational complexity of terminological reasoning in BACK
• Reasoning and revision in hybrid representation systems
• Terminological reasoning is inherently intractable

Cited in

(20)

• Kripke completeness of strictly positive modal logics over meet-semilattices with operators
• CoLab: A hybrid knowledge representation and compilation laboratory
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• Consistency checking reduced to satisfiability of concepts in terminological systems
• Description Logics
• Computing the least common subsumer w.r.t. a background terminology
• Unification of concept terms in description logics
• Generalized modal satisfiability
• An empirical analysis of terminological representation systems
• Complexity results for modal dependence logic
• A sequent calculus for reasoning in four-valued description logics
• scientific article; zbMATH DE number 4166932 (Why is no real title available?)
• Tractable reasoning via approximation
• A refined architecture for terminological systems: Terminology = Schema + Views
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
• Attributive concept descriptions with complements
• The complexity of concept languages
• The complexity of satisfiability for fragments of hybrid logic. I.
• scientific article; zbMATH DE number 140381 (Why is no real title available?)

This page was built for publication: The complexity of existential quantification in concept languages.

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