A logic for feature structures and unification with disjunctive and negative values
Nakazawa, Tsuneko
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/20362
Description
Title
A logic for feature structures and unification with disjunctive and negative values
Author(s)
Nakazawa, Tsuneko
Issue Date
1991
Doctoral Committee Chair(s)
Morgan, Jerry L.
Department of Study
Linguistics
Discipline
Linguistics
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Language, Linguistics
Mathematics
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
