%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "omling96.ltx",
%%%     date      = "17 December 1996",
%%%     time      = "16:49:07 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "00893 122 511 4556",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{OmlinG96}

\title{Constructing Deterministic Finite-State Automata in Recurrent
Neural Networks}

\author{Christian~W. Omlin \and C.~Lee Giles}

\Pages{937--972}

\Month{November}

\Year{1996}

\Volume{43}

\Number{6}

\maketitle

\begin{abstract}

Recurrent neural networks that are \emph{trained} to behave like
deterministic finite-state automata (DFAs) 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
\emph{construct} second-order recurrent neural networks with a sparse
interconnection topology and sigmoidal discriminant function such that
the internal DFA state representations are stable, that is, the
constructed network correctly classifies strings of \emph{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, the constructive algorithm generates a ``programmed'' neural
network with $O(n)$ neurons and $O(mn)$ weights. We compare our
algorithm to other methods in the proposed literature.

\end{abstract}

\begin{categories}

B.2.2 [\textbf{Arithmetic and Logic Structures}]: Performance Analysis
  and Design Aids---\emph{simulation\textup; verification};
F.1.1 [\textbf{Computation by Abstract Devices}]: Models of
  Computation---\emph{automata\textup; relations among models\textup;
  self-modifying machine};
G.1.0 [\textbf{Numerical Analysis}]: General---\emph{stability};
G.1.2 [\textbf{Numerical Analysis}]: Approximation---\emph{nonlinear
  approximation};
I.2.4 [\textbf{Artificial Intelligence}]: Knowledge Representation
  Formalisms and Methods---\emph{representations};
I.5.1 [\textbf{Pattern Recognition}]: Models---\emph{neural nets}

\end{categories}

\begin{terms}

Algorithms, Theory, Verification

\end{terms}

\begin{keywords}

Automata, connectionism, knowledge encoding, neural networks, nonlinear
  dynamics, recurrent neural networks, rules, stability

\end{keywords}

\end{document}