On the implementation of frontier-to-root tree automata in recursive neural networks

In this paper we explore the node complexity of recursive neural network implementations of frontier-to-root tree automata (FRA). Specifically, we show that an FRAO (Mealy version) with m states, l input-output labels, and maximum rank N can be implemented by a recursive neural network with O(radical(log l+log m)lm(N)/log l+N log m) units and four computational layers, i.e., without counting the input layer. A lower bound is derived which is tight when no restrictions are placed on the number of layers. Moreover, we present a construction with three computational layers having node complexity of O((log l + log m)radical lmN) and O((log l + log m) lmN) connections. A construction with two computational layers is given that implements any given FRAO with a node complexity of O(lmN) and O((log l+N log m)lmN) connections. As a corollary we also get a new upper bound for the implementation of finite-state automata (FSA) into recurrent neural networks with three computational layers.