tailieunhanh - Báo cáo khoa học: "An Alternative Conception of Tree-Adjoining Derivation*"

The precise formulation of derivation for treeadjoining 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 reformulated in order to manifest the proper linguistic dependencies in derivations. The particular proposal is both precisely characterizable, through a compilation to linear indexed grammars, and computationally operational, by virtue of an efficient algorithm for recognition and parsing. . | 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 treeadjoining 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 reformulated in order to manifest the proper linguistic dependencies in derivations. The particular proposal is both precisely characterizable through a compilation to linear indexed grammars and computationally operational by virtue of an efficient 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 hierarchical structure that the derivation imposes on the string 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-89-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 Kroch 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 .