TAILIEUCHUNG - Báo cáo khoa học: "Tabular Algorithms for TAG Parsing"

We describe several tabular algorithms for Tree Adjoining G r a m m a r parsing, creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum. | Proceedings of EACL 99 Tabular Algorithms for TAG Parsing Miguel A. Alonso Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain alonso@ Eric de la Clergerie INRIA Domaine de Voluceau Rocquencourt . 105 78153 Le Chesnay Cedex France Abstract We describe several tabular algorithms for Tree Adjoining Grammar parsing creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum. 1 Introduction Tree Adjoining Grammars are a extension of CFG introduced by Joshi in Joshi 1987 that use trees instead of productions as the primary representing structure. Several parsing algorithms have been proposed for this formalism most of them based on tabular techniques ranging from simple bottom-up algorithms Vijay-Shanker and Joshi 1985 to sophisticated extensions of the Earley s algorithm Schabes and Joshi 1988 Schabes 1994 Nederhof 1997 . However it is difficult to inter-relate different parsing algorithms. In this paper we study several tabular algorithms for TAG parsing showing their common characteristics and how one algorithm can be derived from another in turn creating a continuum from simple pure bottom-up to complex predictive algorithms. Formally a TAG is a 5-tuple Q Výv Vr s I A where VXr is a finite set of non-terminal symbols Vt a finite set of terminal David Cabrero Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain cabrero@ Manuel Vilares Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain vilares@ symbols s the axiom of the grammar I a finite set of initial trees and A a finite set of auxiliary trees. luA is the set of elementary trees. Internal nodes are labeled by non-terminals and leaf nodes by terminals or E except for just one leaf

• Báo cáo khoa học
• Tabular Algorithms
• TAG Parsing
• Miguel A
• Alonso
• scientific reports
• model language
• process natural language
• Dialog Control
• Natural Language System
• Dialog Control in a Natural Language System
• Expanding the Horizons
• Natural Language Interfaces
• Phil Hayes
• PROSPECTS OR PRACTICAL
• NATURAL LANGUAGE SYSTEMS
• Workshops
• NATURAL LANGUAGE
• INTERACTION WITH MACHINES
• Long Papers
• COMPUTER INTEBFACE DESIGN MURRAY TUROFF DEPARTMENT OF COMPUTER
• IiVFORMATION SCIENCE IIEW JERSEY INSTITUTE OF TECHNOLOGY
• EVALUATION OF NATURAL LANGUAGE
• INTERFACES TO DATABASE SYSTEMS
• A PANEL DISCUSSION
• database query system
• J
• Norwood Crout
• INTERFACES TO DATA BASE SYSTEMS
• Bozena Henisz
• INTERPRETING NATURAL LANGUAGE
• DATABASE UPDATES
• S
• Jermld Kaplan Jim David
• TRANSPORTABLE NATURAL LANGUAGE
• INTERFACES TO DATABASES
• Gary G
• Hendrlx and William H
• Lewis
• DATABASES THEORETICAL
• TECHNICAL ISSUES
• TRANSPORTABLE NATURAL LANGUAGE INTERFACES
• PROBLEMS AND TECHNIQUES
• Barbara J
• Grosz
• THEORETICAL TECHNICAL ISSUES
• NATURAL LANGUAGE ACCESS TO DATABASES
• R
• Petrick
• Domain Independent
• Database Access Systems
• ISSUES IN NATURAL LANGUAGE
• ACCESS TO DATABASES
• A LOGIC PROGRAMMING PERSPECTIVE
• Sharon C
• Salveter David Maier
• PLANNING NATURAL LANGUAGE
• EXPRESSIONS REFERRING
• Douglas E
• Appelt
• THE TEXT SYSTEM
• NATURAL LANGUAGE GENERATION
• Kathleen R
• M
• MENTING A DATABASE
• KNOWLEDGE REPRESENTATION
• THE KEY TO THE SELECTION PROBLEM
• E
• Jeffrey Conklin David D
• McDonald
• A KNOWLEDGE ENGINEERING
• NATURAL LANGUAGE UNDERSTANDING
• Stuart C
• Shapiro
• NATURAL LANGUAGE TEXTS
• NECESSARILY GRAMMATICAL
• EVEN COMPLETE
• UNGRAMHATICALITY
• EXTRA GRAMMATICALITY
• NATURAL LANGUAGE UNDERSTANDING SYSTEMS
• Taxonomy
• Descriptions
• Individuals in Natural
• Language Understanding
• The Use of Ooject Special Knowledge
• Natural Language Processing
• Mark H
• Bursteln