Neural Computation, Vol 8, 675-696, Copyright © 1996 by The MIT Press

ARTICLES

Stable encoding of large finite-state automata in recurrent neural networks with sigmoid discriminants

CW Omlin and CL Giles
NEC Research Institute, Princeton, NJ 08540, USA.

We propose an algorithm for encoding deterministic finite-state automata (DFAs) in second-order recurrent neural networks with sigmoidal discriminant function and we prove that the languages accepted by the constructed network and the DFA are identical. The desired finite-state network dynamics is achieved by programming a small subset of all weights. A worst case analysis reveals a relationship between the weight strength and the maximum allowed network size, which guarantees finite-state behavior of the constructed network. We illustrate the method by encoding random DFAs with 10, 100, and 1000 states. While the theory predicts that the weight strength scales with the DFA size, we find empirically the weight strength to be almost constant for all the random DFAs. These results can be explained by noting that the generated DFAs represent average cases. We empirically demonstrate the existence of extreme DFAs for which the weight strength scales with DFA size.

This article has been cited by other articles:

				A. Vahed and C.W. Omlin A Machine Learning Method for Extracting Symbolic Knowledge from Recurrent Neural Networks Neural Comput., January 1, 2004; 16(1): 59 - 71. [Abstract] [Full Text] [PDF]

				B. Hammer and P. Tino Recurrent Neural Networks with Small Weights Implement Definite Memory Machines Neural Comput., August 1, 2003; 15(8): 1897 - 1929. [Abstract] [Full Text]

				M. Schmitt On the Complexity of Computing and Learning with Multiplicative Neural Networks Neural Comput., February 1, 2002; 14(2): 241 - 301. [Abstract] [Full Text] [PDF]

				S. C. Kremer Spatiotemporal Connectionist Networks: A Taxonomy and Review Neural Comput., February 1, 2001; 13(2): 249 - 306. [Abstract] [Full Text]

				R. C. Carrasco, M. L. Forcada, M. A. Valdés-Muñoz, and R. P. Ñeco Stable Encoding of Finite-State Machines in Discrete-Time Recurrent Neural Nets with Sigmoid Units Neural Comput., September 1, 2000; 12(9): 2129 - 2174. [Abstract] [Full Text]