On the Computational Power of Recurrent Neural Networks for Structures

Recurrent neural networks can simulate any finite state automata as well as any multi-stack Turing machine. When constraining the network architecture, however, this computational power may no longer hold. For example, recurrent cascade-correlation cannot simulate any finite state automata. Thus, it is important to assess the computational power of a given network architecture, since this characterizes the class of functions which, in principle, can be computed by it. We discuss the computational power of neural networks for structures. Elman-style networks, cascade-correlation networks and neural trees for structures are introduced We show that Elman-style networks can simulate any frontier-to-root tree automation while neither cascade-correlation networks nor neural trees can. As a special case of the latter result, we obtain that neural trees for sequences cannot simulate any finite state machine.