Prior work has focused on using first order RNNs with and without external memory to learn Dyck languages up to length 2 [1]}, [2]}, [3]} but none of them have achieved reasonable performance. However recently [4]} showed the effective mechanism for training memory augmented RNNs and thus achieving reasonable performance on Dyck languages.
In contrast, recent work has focused on a different class of RNNs, often referred to as higher order tensor RNNs, which has demonstrated their ability to learn CFLs, even \(D_2\)  languages, on long sequences that are extend beyond the training distribution [5]}. These models consist of high order tensors and, with finite precision, are theoretically capable of recognizing a PDA of any length. These models are furthermore more interpretable and work across a wide variety of grammars [5]}, [7]}, [8]}. However, due to their computational complexity and also difficulty in training, higher order RNNs are often not used in practice.
In this paper, we focus on investigating the limitations of first order RNNs with finite precision, with and without external memory, for the task of recognizing CFLs of lengths \(n>1\) . Furthermore, we propose several new, improved memory-augmented RNN models, a class we label as the DiffStk-RNN family of RNN models, that can effectively recognize long CFLs.
The contributions of this paper are the following:
