Files in this item



application/pdf9136681.pdf (10MB)Restricted to U of Illinois
(no description provided)PDF


Title:A logic for feature structures and unification with disjunctive and negative values
Author(s):Nakazawa, Tsuneko
Doctoral Committee Chair(s):Morgan, Jerry L.
Department / Program:Linguistics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Language, Linguistics
Computer Science
Abstract:This dissertation proposes a unification-based formalism to provide a common basis for a computational realization of different linguistic theories, GPSG, HPSG, and LFG in particular, both as a means of theory testing and for the purpose of developing natural language processing systems. A logical language, called LFD, is proposed to describe feature structures and unification as common components across different theories.
The goal of the formalism is to provide an efficient computational solution to the unification problem while allowing enough expressive power for common linguistic concepts, such as disjunctive and negative values, and value sharing. The semantics of disjunctive and negative values is reevaluated as constraints on instantiation of unspecified values, and the semantics of negative values is defined in such a way that the satisfiability is monotonic with respect to the subsumption order. An intuitive correspondence between disjunctive and negative values e.g. 'first- OR second-person' and 'NOT third person', is formally captured as logical equivalence, and further extended to complex values.
Underspecification, a central notion in unification-based formalisms and theories, is viewed as a property of the description of feature structures, rather than structures themselves. A special purpose atomic value, called 'unspecified value', is proposed as a primitive expression of LFD. This value plays a crucial role in stating disjunctive values in terms of logically equivalent negative values in the underspecified description of feature structures. Furthermore, this value makes it possible to express obligatory instantiation of values without specifying a particular value, a long-standing problem for which no coherent computational solution has been given.
Any formulas of LFD can be converted to a clausal form similar to Horn clauses, called negative definite clauses, whose satisfiability can be computed in polynomial time. A preprocessed form, called a prefix closure, of formulas to specify value sharing is proposed. Although the conversion of formulas into negative definite clauses could expand the size of input formulas exponentially, thus nullifying the computational efficiency of the clauses, the computational advantage of the proposed approach is shown in the context of consecutive unification operations.
Issue Date:1991
Rights Information:Copyright 1991 Nakazawa, Tsuneko
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9136681
OCLC Identifier:(UMI)AAI9136681

This item appears in the following Collection(s)

Item Statistics