The complexity of concept languages
This paper is dedicated to a formidable problem of artificial intelligence. The main concern of this paper is terminological knowledge representation systems (TKRSs), whose basic feature is to represent knowledge by means of taxonomies, here called terminologies, and to provide a specialized reasoning engine to do inferences on these structures. The communication between the KRS and the rest of the knowledge based systems is realized via queries and answers to queries. The type of language used to represent knowledge, and the inferences drawn from it characterize the KRS. Here are the main contributions of the paper: (1) a complexity analysis of concept satisfiability and subsumption for a wide class of concept languages; (2) algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform [\textit{F. M. Donini}, \textit{B. Hollunder}, \textit{M. Lenzerini}, \textit{A. M. Spaccamela}, \textit{D. Nardi} and \textit{W. Nutt}, The complexity of existential quantification in concept languages, Artificial Intell. 2-3, 309-327 (1992)].
- ``Reducing classic to practice: Knowledge representation theory meets reality
- A guide to completeness and complexity for modal logics of knowledge and belief
- An empirical analysis of terminological representation systems
- Attributive concept descriptions with complements
- Computational complexity of terminological reasoning in BACK
- Foundations of a functional approach to knowledge representation
- scientific article; zbMATH DE number 3986613 (Why is no real title available?)
- scientific article; zbMATH DE number 46359 (Why is no real title available?)
- scientific article; zbMATH DE number 67502 (Why is no real title available?)
- scientific article; zbMATH DE number 67503 (Why is no real title available?)
- scientific article; zbMATH DE number 3559512 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 1142327 (Why is no real title available?)
- scientific article; zbMATH DE number 3274715 (Why is no real title available?)
- Terminological reasoning is inherently intractable
- The complexity of existential quantification in concept languages.
- The Computational Complexity of Provability in Systems of Modal Propositional Logic
- The KL-ONE family
- A refined architecture for terminological systems: Terminology = Schema + Views
- An epistemic operator for description logics
- An empirical analysis of terminological representation systems
- Consistency checking reduced to satisfiability of concepts in terminological systems
- A polynomial space construction of tree-like models for logics with local chains of modal connectives
- EXPtime tableaux for ALC
- Expressiveness of concept expressions in first-order description logics
- The complexity of propositional linear temporal logics in simple cases
- \(\mathcal{ALCQPI}_{R^+}\): rational grading in an expressive description logic with inverse and transitive roles and counting
- Expressivity Hierarchy of Languages for Epistemic Awareness Models
- Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
- A PARAMETERIZED ALGORITHM TO EXPLORE FORMAL CONTEXTS WITH A TAXONOMY
- Camelis: a logical information system to organise and browse a collection of documents
- Ontologies and Databases: The DL-Lite Approach
- Adding clauses to poor man's logic (without increasing the complexity)
- Generalized satisfiability for the description logic \(\mathcal{ALC}\)
- scientific article; zbMATH DE number 67502 (Why is no real title available?)
- scientific article; zbMATH DE number 67503 (Why is no real title available?)
- scientific article; zbMATH DE number 67970 (Why is no real title available?)
- scientific article; zbMATH DE number 140381 (Why is no real title available?)
- Deduction in Concept Languages: from Subsumption to Instance Checking
- scientific article; zbMATH DE number 1869614 (Why is no real title available?)
- scientific article; zbMATH DE number 1405451 (Why is no real title available?)
- Handling Spatial Relations in Logical Concept Analysis to Explore Geographical Data
- 2-Exp Time lower bounds for propositional dynamic logics with intersection
- Complexity of hyperconcepts
- Generalized modal satisfiability
- The complexity of existential quantification in concept languages.
This page was built for publication: The complexity of concept languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363785)
