Representation and reasoning with attributive descriptions.

*(English)*Zbl 0747.68075
Sorts and types in artificial intelligence, Proc. Workshop, Eringerfeld/FRG 1989, Lect. Notes Comput. Sci. 418, 112-139 (1990).

[For the entire collection see Zbl 0743.68016.]

The present paper comes to fill in an existing gap in the rich literature on descriptional languages of linguistic (and AI) information: to establish a bridge between terminological (logics or) representation languages, and feature-based unfication grammars. The commonalities as well as the differences of these two families of attribute description formalisms are established mainly on algebraic and logical bases. This is the real merit of the paper; in Section 2 the authors describe the terminological logics paradigm: representation and reasoning. The main theoretical result is that terminological reasoning (viz. subsumption) is inherently intractable (i.e. PSAPCE-complete), despite of the decidability of the subsumption determination. However, in typical, “normal” cases, it is possible to find well-behaved algorithms. Section 3 provides an original approach to unification grammars: using the strong analogy between logic programs and unification grammars, the last ones are viewed as definite clauses over feature constraint (logic) languages. The paper exhibits a quadratic-time algorithm for solving feature clauses: it consists of a linear-time unfolding phase, followed by a quadratic-time normalization phase.

The present paper comes to fill in an existing gap in the rich literature on descriptional languages of linguistic (and AI) information: to establish a bridge between terminological (logics or) representation languages, and feature-based unfication grammars. The commonalities as well as the differences of these two families of attribute description formalisms are established mainly on algebraic and logical bases. This is the real merit of the paper; in Section 2 the authors describe the terminological logics paradigm: representation and reasoning. The main theoretical result is that terminological reasoning (viz. subsumption) is inherently intractable (i.e. PSAPCE-complete), despite of the decidability of the subsumption determination. However, in typical, “normal” cases, it is possible to find well-behaved algorithms. Section 3 provides an original approach to unification grammars: using the strong analogy between logic programs and unification grammars, the last ones are viewed as definite clauses over feature constraint (logic) languages. The paper exhibits a quadratic-time algorithm for solving feature clauses: it consists of a linear-time unfolding phase, followed by a quadratic-time normalization phase.

Reviewer: N.Curteanu (Iaşi)