tailieunhanh - Báo cáo khoa học: "COMPUTATIONAL PLEXITY AND LEXICAL FUNCTIONAL GRAMMAR"

An important goal of ntodent linguistic theory is to characterize as narrowly as possible the class of natural !anguaooes. An adequate linguistic theory should be broad enough to cover observed variation iu human languages, and yet narrow enough to account for what might be dubbed "cognitive demands" -- among these, perhaps, the demands of lcarnability and pars,ability. If cognitive demands are to carry any real theoretical weight, then presumably a language may be a (theoretically) pos~ible human language, and yet be "inaccessible" because it is not leanmble or pa~able. . | COMPUTA TIONAL COMPLEXITY AND LEXICAL FUNCTIONAL GRAMMAR Robert c. Berwick MIT Artificial Intelligence Laboratory Cambridge MA 1. INTRODUCTION An important goal of modem linguistic theory is to characterize as narrowly as possible the class of natural languages. An adequate linguistic theory should be broad enough to cover observed variation ill human languages and yet narrow enough to account for what might be dubbed cognitive demands -- among these perhaps the demands of learnability and parsability. If cognitive demands arc to carry any real theoretical weight then presumably a language may be a theoretically possible human language and yet be inaccessible because it is not learnable or parsable. Formal results along these lines have already been obtained for certain kinds of Transformational Generative Grammars for example Peters and Ritchie 1J showed that Arpec s-style unrestricted transformational grammars can generate any recursively enumerable set while Rounds 2 3 extended this work by demonstrating that modestly resuicted transformational grammars TGs can generate languages whose recognition time is provably exponential. In Rounds proof transformations are subject to a terminal length non-decreasing condition as suggested by Peters and Myhill. Thus in the worst case TGs generate languages whose recognition is widely recognized to be computationally intractable. Whether this worst case complexity analysis has any real import for actual linguistic study has been the subject of some debate for discussion see Chomsky 4 Berwick and Weinberg 5 . Without resolving that controversy here however one thing can be said to make TGs efficiently parsablc one might provide additional constraints. For instance these additional strictures could be roughly of the sort advocated in Marcus work on parsing 6 -- constraints specifying that TG-based languages must have parsers that meet certain locality conditions . The Marcus constraints apparently amount to an extension of .

• Báo cáo khoa học
• COMPUTATIONAL PLEXITY
• LEXICAL FUNCTIONAL GRAMMAR
• Robert C
• Berwick
• 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