Werner Nutt

I&C Journal 1997 Journal Article

The Complexity of Concept Languages

• Francesco M Donini
• Maurizio Lenzerini
• Daniele Nardi
• Werner Nutt

A basic feature of Terminological Knowledge Representation Systems 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 taxonomy is built through a representation language called aconcept language(ordescription logic), which is given a well-defined set-theoretic semantics. The efficiency of reasoning has often been advocated as a primary motivation for the use of such systems. The main contributions of the paper are: (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.

KER Journal 1995 Journal Article

Reasoning about structured objects: Knowledge representation meets databases

• Franz Baader
• Martin Buchheit
• Manfred A. Jeusfeld
• Werner Nutt

Structured objects are items with defined properties that are to be represented in a computer system. Research in Knowledge Representation (KR) and in Database Design (DB) has produced languages for describing structured objects. Although different in the particular means for defining properties, both areas share the goal of representing a part of the world in a structured way. Moreover, the rise of object-centred formalisms in the last decade has significantly influenced the convergence of languages.

AIJ Journal 1992 Journal Article

The complexity of existential quantification in concept languages

• Francesco M. Donini
• Maurizio Lenzerini
• Daniele Nardi
• Bernhard Hollunder
• Werner Nutt
• Alberto Marchetti Spaccamela

Much of the research on concept languages, which also are called terminological languages, has focused on the computational complexity of subsumption. The intractability results can be divided into two groups. First, it has been shown that extending the basic language jy- with constructs containing some form of logical disjunction leads to co-NP-hard subsumption problems. Secondly, adding negation to jy- makes subsumption PSPACE-complete. The main result of this paper is that extending jy- with unrestricted existential quantification makes subsumption NP-complete. This is the first proof of intractability for a concept language containing, whether explicitly or implicitly, no construct expressing disjunction. Unrestricted existential quantification is therefore, alongside disjunction, a source of computational complexity in concept languages.

ECAI Conference 1990 Conference Paper

Subsumption Algorithms for Concept Description Languages

• Bernhard Hollunder
• Werner Nutt
• Manfred Schmidt-Schauß