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

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

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
• scientific article; zbMATH DE number 1512862

Cites work

• Attributive concept descriptions with complements
• Computational complexity of terminological reasoning in BACK
• 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?)
• Reasoning and revision in hybrid representation systems
• Terminological reasoning is inherently intractable

Cited in

(21)

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

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)