The complexity of concept languages
type: Item
instance of: scholarly article
title: The complexity of concept languages
zbMATH Open document ID: 0906.68145
author: F. M. Donini
author: Maurizio Lenzerini
author: Daniele Nardi
published in: Information and Computation
publication date: 1997-08-11T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68T30
zbMATH DE Number: 1047206
zbMATH Keywords: terminological knowledge representation systems
Wikidata QID: Q58006980
reviewed by: Georgiy E. Tseytlin
MaRDI profile type: Publication
OpenAlex ID: W1980794674
cites work: Q4132480
cites work: ``Reducing'' classic to practice: Knowledge representation theory meets reality
cites work: Q3750100
cites work: The complexity of existential quantification in concept languages.
cites work: Q4012243
cites work: Q3996619
cites work: Q4198056
cites work: A guide to completeness and complexity for modal logics of knowledge and belief
cites work: An empirical analysis of terminological representation systems
cites work: Q4385525
cites work: Q4385543
cites work: The Computational Complexity of Provability in Systems of Modal Propositional Logic
cites work: Foundations of a functional approach to knowledge representation
cites work: Computational complexity of terminological reasoning in BACK
cites work: Terminological reasoning is inherently intractable
cites work: Q4012244
cites work: Attributive concept descriptions with complements
cites work: Q5560258
cites work: The KL-ONE family
DOI: 10.1006/INCO.1997.2625
DBLP publication ID: journals/iandc/DoniniLNN97
description: scientific article; zbMATH DE number 1047206