TAILIEUCHUNG - Báo cáo khoa học: "Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication"

Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual result: CFG parsers running in time O([Gl[w[3-e) on a grammar G and a string w can be used to multiply m x m Boolean matrices in time O(m3-e/3). In the process we also provide a formal definition of parsing motivated by an informal notion due to Lang. Our result establishes one of the first limitations on general CFG parsing: a fast, practical CFG parser would yield a fast, practical BMM algorithm, which is not believed to exist. 1 Introduction The standard method. | Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication Lillian Lee Division of Engineering and Applied Sciences Harvard University 33 Oxford Street Cambridge MA 012138 Abstract Valiant showed that Boolean matrix multiplication BMM can be used for CFG parsing. We prove a dual result CFG parsers running in time 0 G w 3-e on a grammar G and a string w can be used to multiply m X m Boolean matrices in time O m3-e 3 . In the process we also provide a formal definition of parsing motivated by an informal notion due to Lang. Our result establishes one of the first limitations on general CFG parsing a fast practical CFG parser would yield a fast practical BMM algorithm which is not believed to exist. 1 Introduction The context-free grammar CFG formalism was developed during the birth of the field of computational linguistics. The standard methods for CFG parsing axe the CKY algorithm Kasami 1965 Younger 1967 and Earley s algorithm Earley 1970 both of which have a worst-case running time of O gN3 for a CFG in Chomsky normal form of size g and a string of length N. Graham et al. 1980 give a variant of Earley s algorithm which runs in time O gN3 log N . Valiant s parsing method is the asymptotically fastest known Valiant 1975 . It uses Boolean matrix multiplication BMM to speed up the dynamic programming in the CKY algorithm its worst-case running time is O gM NỴ where M m is the time it takes to multiply two m X m Boolean matrices together. The standard method for multiplying matrices takes time O m3 . There exist matrix multiplication algorithms with time complexity O m3-Ổ for instance Strassen s has a worstcase running time of G m281 Strassen 1969 and the fastest currently known has a worst-case running time of ơ m2-376 Coppersmith and Winograd 1990 . Unfortunately the constants involved are so large that these fast algorithms with the possible exception of Strassen s cannot be used in practice. As matrix multiplication is a very .

• Báo cáo khoa học
• Fast Context Free Parsing
• Requires Fast Boolean
• Matrix Multiplication
• 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