TAILIEUCHUNG - Báo cáo khoa học: "CHARACTERIZING STRUCTURAL DESCRIPTIONS PRODUCED BY VARIOUS. GRAMMATICAL FORMALISMS*"

We consider the structural descriptions produced by various grammatical formalisms in ~ of the complexity of the paths and the relationship between paths in the sets of structural descriptions that each system can generate. In considering the relationship between formalisms, we show that it is useful to abstract away from the details of the formalism, and examine the nature of their derivation process as reflected by properties of their deriva:ion trees. We find that several of the formalisms considered can be seen as being closely related since they have derivation tree sets with the same structure as those produced. | CHARACTERIZING STRUCTURAL DESCRIPTIONS PRODUCED BY VARIOUS GRAMMATICAL FORMALISMS K. Vijay-Shanker David J. Weir Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia Pa 19104 ABSTRACT We consider the structural descriptions produced by various grammatical formalisms in terms of the complexity of the paths and the relationship between paths in the sets of structural descriptions that each system can generate. In considering the relationship between formalisms we show that it is useful to abstract away from the details of the formalism and examine the nature of theữ derivation process as reflected by properties of then derivation trees. We find that several of the formalisms considered can be seen as being closely related since they have derivation tree sets with the same structure as those produced by Context-Free Grammars. On the basis of this observation we describe a class of formalisms which we call Linear Context-Free Rewriting Systems and show they are recognizable in polynomial time and generate only semilinear languages. 1 Introduction Much of the study of grammatical systems in computational linguistics has been focused on the weak generative capacity of grammatical formalism. Little attention however has been paid to the structural descriptions that these formalisms can assign to strings . thetf strong generative capacity. This aspect of the formalism is both linguistically and computationally important For example Gazdar 1985 discusses the applicability of Indexed Grammars IG s to Natural Language in terms of the structural descriptions assigned and Berwick 1984 discusses the strong generative capacity of Lexical-Functional Grammar LFG and Government and Bindings grammars GB . The work of Thatcher 1973 and Rounds 1969 define formal systems that generate tree sets that are related to CFG s and IG s. We consider properties of the tree sets generated by CFG s Tree Adjoining Grammars Tag s Head Grammars HG

• Báo cáo khoa học
• CHARACTERIZING STRUCTURAL
• DESCRIPTIONS PRODUCED
• VARIOUS GRAMMATICAL FORMALISMS
• 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