### Constructing deterministic finite-state automata in recurrent neural networksConstructing deterministic finite-state automata in recurrent neural networks

Access Restriction
Subscribed

 Author Omlin, Christian W. ♦ Giles, C. Lee Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1996 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Automata ♦ Connectionism ♦ Knowledge encoding ♦ Neural networks ♦ Nonlinear dynamics ♦ Recurrent neural networks ♦ Rules ♦ Stability Abstract Recurrent neural networks that are $\textit{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 sigmoidel discriminant function together with the recurrent structure contribute to this instability. We prove that a simple algorithm can $\textit{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 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 $\textit{n}$ state and $\textit{m}input$ alphabet symbols, the constructive algorithm generates a “programmed” neural network with $\textit{O}(\textit{n})$ neurons and $\textit{O}(\textit{mn})$ weights. We compare our algorithm to other methods proposed in the literature. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1996-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 43 Issue Number 6 Page Count 36 Starting Page 937 Ending Page 972

#### Open content in new tab

Source: ACM Digital Library