Stable Encoding of Large Finite-State Automata in Recurrent Neural Networks with Sigmoid Discriminants
| dc.contributor.author | Omlin, Christian W. | en_US |
| dc.contributor.author | Giles, C. Lee | en_US |
| dc.date.accessioned | 2004-05-31T22:27:47Z | |
| dc.date.available | 2004-05-31T22:27:47Z | |
| dc.date.created | 1994-12 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | We 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.extent | 283981 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/660 | |
| dc.language.iso | 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 |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3337 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-94-101 | en_US |
| dc.title | Stable Encoding of Large Finite-State Automata in Recurrent Neural Networks with Sigmoid Discriminants | en_US |
| dc.type | Technical Report | en_US |