Browse Prior Art Database

A Unification Method for Disjunctive Feature Descriptions

IP.com Disclosure Number: IPCOM000128675D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 31K

Publishing Venue

Software Patent Institute

Related People

Robert Kasper: AUTHOR [+3]

Abstract

Although disjunction has been used in several uni$cation-based grammar formalisms, existing methods of unification have been unsatisfactory for descriptions containing large quantities of disjunction, because they require exponential time. This paper describes a method of unification by succes-sive approximation, resulting in better average performance.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Unification Method for Disjunctive Feature Descriptions

Robert Kasper

ISI Reprint Serif ISIIRS-87-18 April 198 University of Southern California Reprinted from Proceedings of the 25th Annua Meeting of the Association for Computations! Linguistic: held July 6-9, 1987, in Stanford, California INFORMATION

SCIENCES INSTITUTE 213/822-1511

4676 Admiralty Way/Marina del Rey/California 90292-6695 This research was sponsored in part by the Air Force Office of Scientific Research under Contract Nos. FQ8671-84-01007 and F49620-87-C-0005, and in part by the Defense Advanced Research Projects Agency under Contract No. MDA903-81-C-0335. The opinions expressed here are solely those of the author.

!SI Reprint Series This report is one in a series of reprints of articles and papers written by ISI research staff and published in professional journals and conference proceedings. For a complete list of ISI reports, write to

Document Distribution USC/Information Sciences Institute

4676 Admiralty Way Marina del Rey, CA 90292-6695 USA A Unification Method for Disjunctive Feature Descriptions Robert T. Kasper USC/Information Sciences Institute

46'76 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 and Electrical Engineering and Computer Science Department University of Michigan

Abstract

Although disjunction has been used in several uni$cation-based grammar formalisms, existing methods of unification have been unsatisfactory for descriptions containing large quantities of disjunction, because they require exponential time. This paper describes a method of unification by succes-sive approximation, resulting in better average performance.

1 Introduction

Disjunction has been used in several unification-based gram-mar formalisms to represent alternative structures in descrip-tions of constituents. Disjunction is an essential component of grammatical descriptions in Kay's Functional Unification Grammar (8), and it has been proposed by Karttunen as a linguistically motivated extension to PATR-II (2). In previous work two methods have been used to handle disjunctive descriptions in parsing and other computational applications. The first method requires expanding descriptions to dis-junctive normal form (DNF) so that the entire description can be interpreted as a set of structures, each of which con-tains no disjunction. This method is exemplified by Definite Clause Grammar (8), which eliminates disjunctive terms by expanding each rule containing disjunction into alternative rules. It is also the method used by Kay (7) in parsing PUG. This method works reasonably well for small

University of Southern California Page 1 Dec 31, 1987

Page 2 of 8

A Unification Method for Disjunctive Feature Descriptions

grammars, but it is clearly unsatisfactory for descriptions containing more than a small number of disjunctiona, because the DNF ex-pansion requires an amount of apace which is exponential in the numb...