Parallel parsing of Tree Adjoining Grammars on the Connection Machine |
| |
Authors: | Michael A. Palis David S. L. Wei |
| |
Affiliation: | (1) Department of Computer and Information Science, University of Pennsylvania, 19104-6389 Philadelphia, Pennsylvania;(2) Computer Science Department, Radford University, 24142 Radford, Virginia |
| |
Abstract: | This paper describes a parsing algorithm for Tree Adjoining Grammar (TAG) and its parallel implementation on the Connection Machine. TAG is a formalism for natural language that employs trees as the basic grammar structures. Parsing involves the application of two operations, called adjunction and substitution, to produce derived tree structures. Sequential parsing algorithms for TAGs run in time quadratic in the grammar size, which is impractical for the very large grammars currently being developed for natural language. This paper presents two parallel algorithms, one running in time nearly linear in the grammar size, and the other running in time logarithmic in the grammar size. Both parallel algorithms were implemented on a Connection Machine CM-2 and performance measurements were obtained for varying grammar sizes.This research was supported in part by NSF Grant BNS-9022010, by the ARO Center for Excellence in Artificial Intelligence, University of Pennsylvania, and by the Army High Performance Computing Research Center (AHPCRC), University of Minnesota. |
| |
Keywords: | Parsing tree adjoining grammar natural language parallel algorithms SIMD architectures |
本文献已被 SpringerLink 等数据库收录! |
|