Show simple item record

Stable Encoding of Large Finite-State Automata in Recurrent Neural Networks with Sigmoid Discriminants

dc.contributor.authorOmlin, Christian W.en_US
dc.contributor.authorGiles, C. Leeen_US
dc.description.abstractWe 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 1,000 states. While the theory predicts that the weight strength scales with the DFA size, we find the weight strength to be almost constant for all the experiments. 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. (Also cross-referenced as UMIACS-TR-94-101)en_US
dc.format.extent283981 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3337en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-94-101en_US
dc.titleStable Encoding of Large Finite-State Automata in Recurrent Neural Networks with Sigmoid Discriminantsen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record