# Constructing Deterministic Finite-State Automata in Recurrent Neural Networks

 dc.contributor.author Omlin, Christian W. en_US dc.contributor.author Giles, C. Lee en_US dc.date.accessioned 2004-05-31T22:32:06Z dc.date.available 2004-05-31T22:32:06Z dc.date.created 1995-05 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/723 dc.description.abstract Recurrent neural networks that are {\it 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 {\it construct} second-order recurrent neural networks with a sparse interconnection topology and sigmoidal discriminant function such that the internal DFA state representations are stable, i.e. the constructed network correctly classifies strings of {\it 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 proposed in the literature. Revised in February 1996 (Also cross-referenced as UMIACS-TR-95-50) en_US dc.format.extent 915072 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3460 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-95-50 en_US dc.title Constructing Deterministic Finite-State Automata in Recurrent Neural Networks en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿