TAILIEUCHUNG - Báo cáo khoa học: "THE COMPUTATIONAL DIFFICULTY OF ID/LP PARSING"

.\lodern linguistic theory attributes surface complexity to interacting snbsystems of constraints. ["or instance, the I D LP gr,'unmar formalism separates constraints on immediate dominance from those on linear order. 5hieber's (t983) I D / I . P parsing algorithm shows how to use ID and LP constraints directly in language processing, without expandiqg them into an intcrmrdiate "object g a m m a r . " However, Shieber's purported O(:,Gi 2 .n ~) runtime bound underestimates the tlillicnlty of I D / L P parsing. I D / L P parsing is actually NP-complete, anti the worst-case runtime of. | THE COMPUTATIONAL DIFFICULTY OF ID LP PARSING G. Edward Barton Jr. . Artificial Intelligence Laboratory 545 Technology Square Cambridge MA 02139 ABSTRACT Modern linguistic theory attributes surface complexity to interacting subsystems of constraints. For instance the ID LP grammar formalism separates constraints on immediate dominance from those on linear order. Shieber s 1983 ID LP parsing algorithm shows how to use ID and LP constraints directly in language processing without expanding them into an intcrmid object grammar. However Shtebers purported O Gị n3 runtime bound underestimates t he di liculty of ID LP parsing. ID LP parsing is actually NP-complcte and the worst-case runtime of Shicber s algorithm is actually exponential in grammar size. The growth of parser data structures causes the difficulty. Some computational and linguistic implications follow in particular it is important to note that despite its potential for combinatorial explosion Shieber s algorithm remains better than the alternative of parsing an expanded object grammar. INTRODUCTION .ecent linguistic theories derive surface complexity from modular subsystems of constraints Chomsky 1981 5 proposes separate theories of bounding government -marking and so forth while Gazdar and Pullum s GPSG formalism Shieber. I983 2lf uses immediate-dominance ID rules linear-precedence constraints and metarules. When modular constraints are involved rule systems that multiply out their surface effects are large and clumsy see Barton. 1984a . The expanded context-free object grammar that multiplies out the constraints in a typical GPSG system would contain trillions of rules Shieber 1983 1 . Sliicbcr 11983 thus leads in a welcome direction by Lowing how ÍD LP grammars can be parsed directly without the combinatorially explosive step of multiplying out the effects of the ID and LI constraints. Shiebcr s algorithm applies ID and LP constraints one step at a time. as needed. However some doubts about

• Báo cáo khoa học
• THE COMPUTATIONAL DIFFICULTY
• ID LP PARSING
• G
• Edward Barton
• 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