Bounds on the complexity of recurrent neural network implementations of finite state machines

Although there are many ways to measure efficiency, we shall be concerned with node complexity, which as its name implies, is a calculation of the required number of nodes. Node complexity is a useful measure of efficiency since the amount of resources required to implement or even simulate a recurrent neural network is typically related to the number of nodes. Node complexity can also be related to the efficiency of learning algorithms for these networks and perhaps to their generalization ability as well. We shall focus on the node complexity of recurrent neural network implementations of finite state machines (FSMs) when the nodes of the network are restricted to threshold logic units.