Bounds on the complexity of recurrent neural network implementations of finite state machines
Bill G. Horne, Don R. Hush · Neural Information Processing Systems · 1993
In this paper the efficiency of recurrent neural network implementations of m-state finite state machines will be explored. Specifically, it will be shown that the node complexity for the unrestricted case can be bounded above by O (√m). It will also be shown that the node complexity is O (√m log m) when the weights and thresholds are restricted to the set {-1, 1}, and O (m) when the fan-in is restricted to two. Matching lower bounds will be provided for each of these upper bounds assuming that the state of the FSM can be encoded in a subset of the nodes of size [log m].