tailieunhanh - Báo cáo khoa học: "REVERSIBLE AUTOMATA AND INDUCTION OF THE ENGLISH AUXILIARY SYSTEM"

M I T ArtificialIntelligenceLaboratory 545 Technology Square Cambridge, M A 02139, U S A ABSTRACT In this paper we apply some recent work of Angluin (1982) to the induction of the English auxiliary verb system. In general, the induction of finiteautomata is computationally intractable. However, Angluin shows that restricted finite automata, the It-reversible automata, can be learned by el~cient (polynomial time) algorithms. W e present an explicit computer model demonstrating that the English auxiliary verb system can in fact be learned as a I-reversible automaton, and hence in a computationally feasibleamount of time. The entire system can be acquired. | REVERSIBLE AUTOMATA AND INDUCTION OF THE ENGLISH AUXILIARY SYSTEM Samuel F. Pilato Robert c. Berwick MIT Artificial Intelligence Laboratory 545 Technology Square Cambridge MA 02139 USA ABSTRACT In this paper we apply some recent work of Angluin 1982 to the induction of the English auxiliary verb system. In general the induction of finite automata is computationally intractable. However Angluin shows that restricted finite automata the k-reversible automata can be learned by efficient polynomial time algorithms. We present an explicit computer model demonstrating that the English auxiliary verb system can in fact be learned as a 1-reversible automaton and hence in a computationally feasible amount of time. The entire system can be acquired by looking at only half the possible auxiliary verb sequences and the pattern of generalization seems compatible with what is known about human acquisition of auxiliaries. We conclude that certain linguistic subsystems may well be learnable by inductive inference methods of this kind and suggest an extension to context-free languages. INTRODUCTION Formal inductive inference methods have rarely been applied to actual natural language systems. Linguists generally suppose that languages are easy to learn because grammars are highly constrained no general purpose inductive inference methods are required. This assumption has generally led to fruitful insights on the nature of grammars. Yet it remains to determine whether all of a language is learned in a grammar-specific manner. In this paper we show how to successfully apply one computationally efficient inductive inference algorithm to the acquisition of a domain of English syntax. Our results suggest that particular language subsystems can be learned bj general induction procedures given certain general constraints. The problem is that these methods are in general computationally intractable. Even for regular languages induction can be exponentially difficult Gold 1978 . This .

• Báo cáo khoa học
• REVERSIBLE AUTOMATA AND INDUCTION
• THE ENGLISH AUXILIARY SYSTEM
• Samuel F
• Pilato 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