Inductive Inference of Regular Grammars Using Recurrent Networks: A Critical Analysis

Many researchers have recently explored the use of recurrent networks for the inductive inference of regular grammars from positive and negative examples [5, 9, 11] with very promising results. In this paper, we give a set of weight constraints guaranteeing that a recurrent network behave as an automaton and show that the measure of this admissible set decreases progressively as the network dimension increases, thus suggesting that automata behavior becomes more and more unlikely for "large" networks. As a result, problems of inductive inference of regular grammars from "long" strings are likely not to be afforded effectively with "large" networks. We suggest looking for more valuable approaches based on the divide et impera paradigm that allow us to limit the network dimensions [3]. 1 Introduction Recently, many researchers have used recurrent neural networks for performing inductive inference of regular grammars with very promising results [5, 9, 11]