TAILIEUCHUNG - Báo cáo khoa học: "POLYNOMIAL TIME PARSING OF COMBINATORY CATEGORIAL GRAMMARS*"

In this paper we present a polynomial time parsing algorithm for Combinatory Categorial Grammar. The recognition phase extends the CKY algorithm for CFG. The process of generating a representation of the parse trees has two phases. Initially, a shared forest is build that encodes the set of all derivation trees for the input string. This shared forest is then pruned to remove all spurious ambiguity. | POLYNOMIAL TIME PARSING OF COMBINATORY CATEGORIAL GRAMMARS K. Vijay-Shanker Department of CIS University of Delaware Delaware DE 19716 David J. Weir Department of EECS Northwestern University Evanston IL 60208 Abstract In this paper we present a polynomial time parsing algorithm for Combinatory Categorial Grammar. The recognition phase extends the CKY algorithm for CFG- The process of generating a representation of the parse trees has two phases. Initially a shared forest is build that encodes the set of all derivation trees for the input string. This shared forest is then pruned to remove all spurious ambiguity. 1 Introduction Combinatory Categorial Grammar CCG 7 5 is an extension of Classical Categorial Grammar in which both function composition and function application are allowed. In addition forward and backward slashes are used to place conditions on the relative ordering of adjacent categories that are to be combined. There has been considerable interest in parsing strategies for CCG 4. 11 8 2 . One of the major problems that must be addressed is that of spurious ambiguity. This refers to the possibility that a CCG can generate a large number of exponentially many derivation trees that assign the same function argument structure to a string. In 9 we noted that a CCG can also generate exponentially many genuinely ambiguous non-spurious derivations. This constitutes a problem for the approaches cited above since it results in their respective algorithms taking exponential time in the worst case. The algorithm we present is the first known polynomial time parser for CCG. The parsing process has three phases. Once the recognizer decides in the first phase that an input can be generated by the given CCG the set of parse This work was partially supported by NSF grant IRI-8909810. We are very grateful to Aravind Joshi Michael Niv Mark Steedman and Kent Wittenberg for helpful discussions. trees can be extracted in the second phase. Rather than enumerating all parses

• Báo cáo khoa học
• POLYNOMIAL TIME PARSING
• COMBINATORY CATEGORIAL GRAMMARS
• K
• Vijay Shanker
• scientific reports
• model language
• process natural language
• A Polynomial Time Parsing Algorithm
• TT MCTAG
• Laura Kallmeyer
• báo cáo khoa học
• báo cáo ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Polynomial Time
• Space Shift Reduce Parsing
• Arbitrary Context free Grammars
• mô hình ngôn ngữ
• 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