TR available from neuroprose archive

[omlinc@cs.rpi.edu]

FTP-host: archive.cis.ohio-state.edu
FTP-filename: /pub/neuroprose/omlin.dfa_encoding.ps.Z
  

The following paper is now available from the neuroprose archive. Please
send your comments regarding the paper to omlinc at cs.rpi.edu. 

-Christian


	  Constructing Deterministic Finite-State Automata
       		   in Recurrent Neural Networks


	     Christian W. Omlin (a,b), C. Lee Giles (a,c)

   (a) NEC Research Institute, 4 Independence Way, Princeton, NJ 08540 
   (b) CS Department, Rensselaer Polytechnic Institute, Troy, NY 12180 
       (c) UMIACS, University of Maryland, College Park, MD 20742 


			      Abstract

Recurrent neural networks that are trained to behave like deterministic 
finite-state automata (DFA's) can show deteriorating performance when
tested on long strings. This deteriorating performance can be attributed 
to the instability of the internal representation of the learned DFA states.
The use of a sigmoidal discriminant function together with the recurrent
structure contribute to this instability. We prove that a simple algorithm
can construct second-order recurrent neural networks with a sparse inter-
connection topology and sigmoidal discriminant function such that the 
internal DFA state representations are stable, i.e. the constructed network 
correctly classifies strings of arbitrary length. The algorithm is based on 
encoding strengths of weights directly into the neural network. We derive a 
relationship between the weight strength and the number of DFA states for
robust string classification. For a DFA with n states and m input alphabet 
symbols and m input alphabet symbols, the constructive algorithm generates 
a "programmed" neural network with  n+1 neurons and  O(mn) weights. We
compare out algorithm to other methods proposed in the literature.

(23 pages, 9 figures, 2 tables)

This paper is also available as Technical Report No. 94-3, Computer Science 
Department, Rensselaer Polytechnic Institute, Troy, NY 12180.