IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

A logic for feature structures and unification with disjunctive and negative values

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/20362

Files in this item

File Description Format
PDF 9136681.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
Discipline: Linguistics
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Dissertation
Subject(s): Language, Linguistics Mathematics 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
Type: Text
Language: English
URI: http://hdl.handle.net/2142/20362
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)

Show full item record

Item Statistics

  • Total Downloads: 0
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key