TAILIEUCHUNG - Báo cáo khoa học: "REVISED GENERALIZED PHRASE STRUCTURE GRAMMAR"

Ristad (1986a) examines the computational complexity of two components of the G P S G formal system (metarules and the feature system) and shows how each of these systems can lead to computational intractability. Rlstad also proves that the universal recognition problem for G P S G s is E X P - P O L Y hard, and In another words, the fastest recognition algorithm for G P S G s can take more than exponential time. These results m a y appear surprising, given GPSG's weak context-fres generative power. . | REVISED GENERALIZED PHRASE STRUCTURE GRAMMAR Eric Sven Ristad1 . Artificial Intelligence Lab 545 Technology Square S05 Cambridge MA 02139 ABSTRACT In this paper I revise generalized phrase structure grammar GPSG linguistic theory so that it is more tractable and linguistically constrained. Revised GPSG is also easier to understand use and implement. I provide an account of topicalization explicative pronouns and parasitic gaps in the revised system and conclude with suggestions for efficient parser design. 1 Introduction and Motivation A linguistic theory specifies a computational process that assigns structural descriptions to utterances. This process requires certain computational resources such as time or space. In a descriptively adequate linguistic theory the computational resources available to the theory match those used by the ideal speakerhearer. The goal of this paper is to revise generalized phrase structure grammar GPSG so that its computational power corresponds to the ability of the speaker-hearer. The bulk of this paper is devoted to identifying what computational resources are used by GPSG theory and deciding whether they are linguistically necessary. GPSG contains five formal devices each of which provides the theory with the resources to model some linguistic phenomenon or ability. I identify those aspects of each device that cause intractability and then restrict the computational power of each device to more closely match the inherent complexity of the phenomenon or ability it models. The remainder of the paper presents the new formal system and exercises it in the domain of topicalization explicative pronouns and parasitic gaps. I conclude with suggestions for efficient parser design and future research. In my opinion the primary value of this work lies in the result revised GPSG or RGPSG as well as in the methodology of using complexity analysis to improve linguistic theories. The methodology explicates how a tool of modern computer .

• Báo cáo khoa học
• REVISED GENERALIZED PHRASE
• STRUCTURE GRAMMAR
• Eric Sven Rlstad
• 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