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(root(log l+log m)lmN/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) root lm(N)) and O((log l + log m) l m(N)) connections. A construction with two computational layers is given that implements any given FRAO with a node complexity of O(lm(N)) and O((log l + N log m)lm(N)) 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.