An Alternative Conception of Tree-Adjoining Derivation

An Alternative Conception of Tree-Adjoining Derivation* Yves Schabes Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 Stuart M. Shieber Aiken Computation Laboratory Division of Applied Sciences Harvard University Cambridge, MA 02138 Abstract The precise formulation of derivation for tree- adjoining grammars has important ramifications for a wide variety of uses of the formalism, from syntactic analysis to semantic interpretation and statistical language modeling. We argue that the definition of tree-adjoining derivation must be re- formulated in order to manifest the proper linguis- tic dependencies in derivations. The particular proposal is both precisely characterizable, through a compilation to linear indexed grammars, and computationally operational, by virtue of an ef- ficient algorithm for recognition and parsing. 1 Introduction In a context-free grammar, the derivation of a string in the rewriting sense can be captured in a single canonical tree structure that abstracts all possible derivation orders. As it turns out, this derivation tree also corresponds exactly to the hi- erarchical structure that the derivation imposes on the str!ng, the derived tree structure of the string. The formalism of tree-adjoining grammars (TAG), on the other hand, decouples these two notions of derivation tree and derived tree. Intuitively, the derivation tree is a more finely grained structure *The authors are listed in alphabetical order. The first author was supported in part by DARPA Grant N0014- 90-31863, ARO Grant DAAL03-S9-C-0031 and NSF Grant IRI90-16592. The second author was supported in part by Presidential Young Investigator award IRI-91-57996 from the National Science Foundation. The authors wish to thank Aravind Joshi for his support of the research, and Aravind Joshi, Anthony Kroeh, Fernando Pereira, and K. Vijay-Shanker for their helpful discussions of the issues involved. We are indebted to David Yarowsky for aid in the design of the experiment mentioned in footnote 5 and for its execution. 167 than the derived tree, and as such can serve as a substrate on which to pursue further analysis of the string. This intuitive possibility is made man- ifest in several ways. Fine-grained syntactic anal- ysis can be pursued by imposing on the deriva- tion tree further combinatoriM constraints, for instance, selective adjoining constraints or equa- tional constraints over feature structures. Statis- tical analysis can be explored through the speci- fication of derivational probabilities as formalized in stochastic tree-adjoining grammars. Semantic analysis can be overlaid through the synchronous derivations of two TAGs. All of these methods rely on the derivation tree as the source of the important primitive relation- ships among trees. The decoupling of derivation trees from derived trees thus makes possible a more flexible ability to pursue these types of anal- yses. At the same time, the exact definition of derivation becomes of paramount importance. In this paper, we argue that previous definitions of tree-adjoining derivation have not taken full ad- vantage of this decoupling, and are not as appro- priate as they might be for the kind of further analysis that tree-adjoining analyses could make possible. In particular, the standard definition of derivation, …

Content truncated to 500 words