A Treatment of Negative Descriptions of Typed Feature Structures

A TREATMENT OF NEGATIVE DESCRIPTIONS OF TYPED FEATURE STRUCTURES KIYOSHI KOGURE NTT Basic P~esearch Laboratories 9-11, Midori-cho 3-chome, Musashino-shi, Tokyo, 180 Japan kogure@atom.ntt.jp Abstract A formal treatment of typed feature structures (TFSs) is developed to augment TFSs, so that neg- ative descriptions of them can be treated. Negative descriptions of TFSs can make linguistic descriptions compact and thus easy to understand. Negative de- scriptions can be classified into three primitive nega- tive descriptions: (1) negations of type symbols, (2) negations of feature existences, and (3) negations of feature-address value agreements. The formalization proposed in this paper is based on A'it-Kaci's com- plex terms. The first description is treated by extend- ing type symbol lattices to include complement type symbols. The second and third are treated by aug- meriting term structures with structures representing these negations. Algorithrrts for augmented-TFS uni- fication have been developed using graph unification, and programs using these algorithms have been writ- ten in Conmaon Lisp. 1 Introduction In unification-based or information:based linguistic frameworks, the most important objects are struc- tures called 'feature structures' (FSs), which are used to describe linguistic objects and phenomena. A fea- ture structure is either atomic or complex: an atomic FS is denoted by an atomic symbol; a complex FS consists of a set of feature-value pairs each of which describes an aspect of an object. Partial information on aJ~ object is merged by applying the unification operation to FSs. ILeseareh on unification-based linguistic theories has been accompanied by research on FSs themselves. Several extensions on FSs or on feature descriptions and formal treatments of the extensions have been proposed. Disjunctive and negative descriptions on FSs help make the linguistic descriptions simple, compact, and thus easy to understand. For disjunctive feature de- acrq)tions, Kay[14] introduces them into FUG (lqlnc- tmnal Unification Grammar) and gives the procedu- ral semantics. Karttunen[ll] also proposes proce- dural treatments of disjunctions in conjunction with relatively simple negations. ILounds and Ka.sper[19, 13] propose a logic-based formalism--feature logic- which uses automata to model FSs and can treat dis- Junctive feature descriptions, and they obtain impor- tant results. For negative descriptions of PSs, one of the most. fundamental properties of FSs, the partiality of in- formation they carry, makes its insufficient to adopt relatively simple treatments. Classical interpretation of negation, for example, does not, allow evaluation of negations to be freely interleaved with unification. Moshier and Rounds[17] propose a formal framework which treats negative feature descriptions on the b`a~is of intuitionistic logic. Ilowever, their |bHnalism has trouble treating double negations. Dawar[5] l)rOl)OSeS a formal treatment b~ed on three-valued logic. In order to treat feature domains of complex FSs and to treat taxonomic hierarchies of symbolic tim ture values, type (or sort) hierarchies have been in- troduced, allowing definition of typed (or sorted) feature-structures (TFSs). A TFS consists of a type symbol from a lattice and a set of rearm:e-value pairs. A TFS can be seen as a generalized concept of both atomic and cornplex FSs. Pollard and Sag/18] iatt'o- duce sorts …

Content truncated to 500 words