Recursive Neural Networks and Automata

Recursive neural networks are computational models that can be used to pro- cess structured data. In particular recurrent neural networks can be trained to process temporal sequences following the rules embedded in a set of examples. Their computation relies on a set of real-valued state and input variables which are processed using a set of continuous operators such as multipliers, adders, and sigmoidal functions. Despite of their strictly continuous nature, many researchers have also investigated interesting symbolic aspects related to their continuous nonlinear dynamics (see e.g. [1-3]), trying to understand the relationships be- tween these models and the classical symbolic computational models, like Turing machines and Finite-State Automata (FSA). The use of real-valued variables seems to provide these models with an unbounded quantity of memory capacity whose effective use is mainly restricted by the functions used to update them and to compute the output sequence.