Paper: Reversible Automata And Induction Of The English Auxiliary System

ACL ID P85-1009
Title Reversible Automata And Induction Of The English Auxiliary System
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1985
Authors

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 computation- ally intractable. However, Angluin shows that restricted finite automata, the It-reversible automata, can be learned by el~cient (polynomial time) algorithms. We present an ex- plicit computer model demonstrating that the English aux- iliary verb system can in fact be learned as a I-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 pat- tern of generalization seems compatible with what is known about human acquisition of auxiliaries. We conclude that certain linguistic subsystems may well...