TAILIEUCHUNG - Báo cáo khoa học: "Graph-structured Stack and Natural Language Parsing"

A general device for handling nondeterminism in stack operations is described. The device, called a Graph-structured Stack, can eliminate duplication of operations throughout the nondeterministic processes. This paper then applies the graph-structured stack to various natural language parsing methods, including ATN, LR parsing, categodal grammar and principlebased parsing. The relationship between the graphstructured stack and a chart in chart parsing is also discussed. | Graph-Structured stack and Natural Language Parsing Masaru Tomlta Center for Machine Translation and Computer Science Department Carnegie-Mellon University Pittsburgh PA 15213 Abstract A general device for handling nondeterminism in stack operations is described. The device called a Graph-structured stack can eliminate duplication of operations throughout the nondeterministic processes. This paper then applies the graph-structured stack to various natural language parsing methods including ATN LR parsing categorial grammar arid principlebased parsing. The relationship between the graph-structured stack and a chart in chart parsing Is also discussed. 1. Introduction A stack plays an important role In natural language parsing. It is the stack which gives a parser context-free rather than regular power by permitting recursions. Most parsing systems make explicit use of the stack. Augmented Transition Network ATN 10 employs a stack for keeping track of return addresses when It visits a sub-network. Shift-reduce parsing uses a stack as a primary device sentences are parsed only by pushing an element onto the stack or by reducing the stack in accordance with grammatical rules. Implementation of principle-based parsing 9 1 4 and categorial grammar 2 also often requires a stack for storing partial parses already built Those parsing systems usually introduce backtracking or pseudo parallelism to handle nondeterminism taking exponential time in the worst case. This paper describes a general device a graph-structured stack. The graph-structured stack was originally introduced in Tomita s generalized LR parsing algorithm 7 8 . This paper applies the graph-structured stack to various other parsing methods. Using the graph-structured stack a system is guaranteed not to replicate the same work and can run In polynomial time. This is true for all of the parsing systems mentioned above ATN shlft-reduce parsing principle-based parsing and perhaps any other parsing systems which .

• Báo cáo khoa học
• Graph structured Stack
• Natural Language Parsing
• Masaru Tomlta
• 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