Sequential Neural Networks as Automata

Abstract: This work attempts to explain the types of computation that neural networks can perform by relating them to automata. We first define what it means for a real-time network with bounded precision to accept a language. A measure of network memory follows from this definition. We then characterize the classes of languages acceptable by various recurrent networks, attention, and convolutional networks. We find that LSTMs function like counter machines and relate convolutional networks to the subregular hierarchy. Overall, this work attempts to increase our understanding and ability to interpret neural networks through the lens of theory. These theoretical insights help explain neural computation, as well as the relationship between neural networks and natural language grammar.

In recent years, neural networks have achieved tremendous success on a variety of natural language processing (NLP) tasks. Neural networks employ continuous distributed representations of linguistic data, which contrast with classical discrete methods. While neural methods work well, one of the downsides of the distributed representations that they utilize is interpretability. It is hard to tell what kinds of computation a model is capable of, and when a model is working, it is hard to tell what it is doing.
This work aims to address such issues of interpretability by relating sequential neural networks to forms of computation that are more well understood. In theoretical computer science, the computational capacities of many different kinds of automata formalisms are clearly established. Moreover, the Chomsky hierarchy links natural language to such automata-theoretic languages BIBREF0 . Thus, relating neural networks to automata both yields insight into what general forms of computation such models can perform, as well as how such computation relates to natural language grammar.
Recent work has begun to investigate what kinds of automata-theoretic computations various types of neural networks can simulate. BIBREF1 propose a connection between long short-term memory networks (LSTMs) and counter automata. They provide a construction by which the LSTM can simulate a simplified variant of a counter automaton. They also demonstrate that LSTMs can learn to increment and decrement their cell state as counters in practice. BIBREF2 , on the other hand, describe a connection between the gating mechanisms of several recurrent neural network (RNN) architectures and weighted finite-state acceptors.
This paper follows BIBREF1 by analyzing the expressiveness of neural network acceptors under asymptotic conditions. We formalize asymptotic language acceptance, as well as an associated notion of network memory. We use this theory to derive computation upper bounds and automata-theoretic characterizations for several different kinds of recurrent neural networks section:rnns, as well as other architectural variants like attention section:attention and convolutional networks (CNNs) section:cnns. This leads to a fairly complete automata-theoretic characterization of sequential neural networks.
In section:experiments, we report empirical results investigating how well these asymptotic predictions describe networks with continuous activations learned by gradient descent. In some cases, networks behave according to the theoretical predictions, but we also find cases where there is gap between the asymptotic characterization and actual network behavior.
Still, discretizing neural networks using an asymptotic analysis builds intuition about how the network computes. Thus, this work provides insight about the types of computations that sequential neural networks can perform through the lens of formal language theory. In so doing, we can also compare the notions of grammar expressible by neural networks to formal models that have been proposed for natural language grammar.
To investigate the capacities of different neural network architectures, we need to first define what it means for a neural network to accept a language. There are a variety of ways to formalize language acceptance, and changes to this definition lead to dramatically different characterizations.
In their analysis of RNN expressiveness, BIBREF3 allow RNNs to perform an unbounded number of recurrent steps even after the input has been consumed. Furthermore, they assume that the hidden units of the network can have arbitrarily fine-grained precision. Under this very general definition of language acceptance, BIBREF3 found that even a simple recurrent network (SRN) can simulate a Turing machine.
We want to impose the following constraints on neural network computation, which are more realistic to how networks are trained in practice BIBREF1 :
Informally, a neural sequence acceptor is a network which reads a variable-length sequence of characters and returns the probability that the input sequence is a valid sentence in some formal language. More precisely, we can write:
[Neural sequence acceptor] Let INLINEFORM0 be a matrix representation of a sentence where each row is a one-hot vector over an alphabet INLINEFORM1 . A neural sequence acceptor INLINEFORM2 is a family of functions parameterized by weights INLINEFORM3 . For each INLINEFORM4 and INLINEFORM5 , the function INLINEFORM6 takes the form INLINEFORM7 
In this definition, INLINEFORM0 corresponds to a general architecture like an LSTM, whereas INLINEFORM1 represents a specific network, such as an LSTM with weights that have been learned from data.
In order to get an acceptance decision from this kind of network, we will consider what happens as the magnitude of its parameters gets very large. Under these asymptotic conditions, the internal connections of the network approach a discrete computation graph, and the probabilistic output approaches the indicator function of some language fig:acceptanceexample.
[Asymptotic acceptance] Let INLINEFORM0 be a language with indicator function INLINEFORM1 . A neural sequence acceptor INLINEFORM2 with weights INLINEFORM3 asymptotically accepts INLINEFORM4 if INLINEFORM5 
Note that the limit of INLINEFORM0 represents the function that INLINEFORM1 converges to pointwise.
Discretizing the network in this way lets us analyze it as an automaton. We can also view this discretization as a way of bounding the precision that each unit in the network can encode, since it is forced to act as a discrete unit instead of a continuous value. This prevents complex fractal representations that rely on infinite precision. We will see later that, for every architecture considered, this definition ensures that the value of every unit in the network is representable in INLINEFORM0 bits on sequences of length INLINEFORM1 .
It is important to note that real neural networks can learn strategies not allowed by the asymptotic definition. Thus, this way of analyzing neural networks is not completely faithful to their practical usage. In section:experiments, we discuss empirical studies investigating how trained networks compare to the asymptotic predictions. While we find evidence of networks learning behavior that is not asymptotically stable, adding noise to the network during training seems to make it more difficult for the network to learn non-asymptotic strategies.
Consider a neural network that asymptotically accepts some language. For any given length, we can pick weights for the network such that it will correctly decide strings shorter than that length (thm:arbitraryapproximation).
Analyzing a network's asymptotic behavior also gives us a notion of the network's memory. BIBREF1 illustrate how the LSTM's additive cell update gives it more effective memory than the squashed state of an SRN or GRU for solving counting tasks. We generalize this concept of memory capacity as state complexity. Informally, the state complexity of a node within a network represents the number of values that the node can achieve asymptotically as a function of the sequence length INLINEFORM0 . For example, the LSTM cell state will have INLINEFORM1 state complexity (thm:lstmmemorybound), whereas the state of other recurrent networks has INLINEFORM2 (thm:SRNmemorybound).
State complexity applies to a hidden state sequence, which we can define as follows:
[Hidden state] For any sentence INLINEFORM0 , let INLINEFORM1 be the length of INLINEFORM2 . For INLINEFORM3 , the INLINEFORM4 -length hidden state INLINEFORM5 with respect to parameters INLINEFORM6 is a sequence of functions given by INLINEFORM7 
Often, a sequence acceptor can be written as a function of an intermediate hidden state. For example, the output of the recurrent layer acts as a hidden state in an LSTM language acceptor. In recurrent architectures, the value of the hidden state is a function of the preceding prefix of characters, but with convolution or attention, it can depend on characters occurring after index INLINEFORM0 .
The state complexity is defined as the cardinality of the configuration set of such a hidden state:
[Configuration set] For all INLINEFORM0 , the configuration set of hidden state INLINEFORM1 with respect to parameters INLINEFORM2 is given by INLINEFORM3 
where INLINEFORM0 is the length, or height, of the sentence matrix INLINEFORM1 .
[Fixed state complexity] For all INLINEFORM0 , the fixed state complexity of hidden state INLINEFORM1 with respect to parameters INLINEFORM2 is given by INLINEFORM3 
[General state complexity] For all INLINEFORM0 , the general state complexity of hidden state INLINEFORM1 is given by INLINEFORM2 
To illustrate these definitions, consider a simplified recurrent mechanism based on the LSTM cell. The architecture is parameterized by a vector INLINEFORM0 . At each time step, the network reads a bit INLINEFORM1 and computes ft = (1 xt)
it = (2 xt)
ht = ft ht-1 + it .
When we set INLINEFORM0 , INLINEFORM1 asymptotically computes the sum of the preceding inputs. Because this sum can evaluate to any integer between 0 and INLINEFORM2 , INLINEFORM3 has a fixed state complexity of DISPLAYFORM0 
However, when we use parameters INLINEFORM0 , we get a reduced network where INLINEFORM1 asymptotically. Thus, DISPLAYFORM0 
Finally, the general state complexity is the maximum fixed complexity, which is INLINEFORM0 .
For any neural network hidden state, the state complexity is at most INLINEFORM0 (thm:generalstatecomplexity). This means that the value of the hidden unit can be encoded in INLINEFORM1 bits. Moreover, for every specific architecture considered, we observe that each fixed-length state vector has at most INLINEFORM2 state complexity, or, equivalently, can be represented in INLINEFORM3 bits.
Architectures that have exponential state complexity, such as the transformer, do so by using a variable-length hidden state. State complexity generalizes naturally to a variable-length hidden state, with the only difference being that INLINEFORM0 def:hiddenstate becomes a sequence of variably sized objects rather than a sequence of fixed-length vectors.
Now, we consider what classes of languages different neural networks can accept asymptotically. We also analyze different architectures in terms of state complexity. The theory that emerges from these tools enables better understanding of the computational processes underlying neural sequence models.
As previously mentioned, RNNs are Turing-complete under an unconstrained definition of acceptance BIBREF3 . The classical reduction of a Turing machine to an RNN relies on two unrealistic assumptions about RNN computation BIBREF1 . First, the number of recurrent computations must be unbounded in the length of the input, whereas, in practice, RNNs are almost always trained in a real-time fashion. Second, it relies heavily on infinite precision of the network's logits. We will see that the asymptotic analysis, which restricts computation to be real-time and have bounded precision, severely narrows the class of formal languages that an RNN can accept.
The SRN, or Elman network, is the simplest type of RNN BIBREF4 :
[SRN layer] DISPLAYFORM0 
A well-known problem with SRNs is that they struggle with long-distance dependencies. One explanation of this is the vanishing gradient problem, which motivated the development of more sophisticated architectures like the LSTM BIBREF5 . Another shortcoming of the SRN is that, in some sense, it has less memory than the LSTM. This is because, while both architectures have a fixed number of hidden units, the SRN units remain between INLINEFORM0 and 1, whereas the value of each LSTM cell can grow unboundedly BIBREF1 . We can formalize this intuition by showing that the SRN has finite state complexity:
[SRN state complexity] For any length INLINEFORM0 , the SRN cell state INLINEFORM1 has state complexity INLINEFORM2 
For every INLINEFORM0 , each unit of INLINEFORM1 will be the output of a INLINEFORM2 . In the limit, it can achieve either INLINEFORM3 or 1. Thus, for the full vector, the number of configurations is bounded by INLINEFORM4 .
It also follows from thm:SRNmemorybound that the languages asymptotically acceptable by an SRN are a subset of the finite-state (i.e. regular) languages. thm:srnlowerbound provides the other direction of this containment. Thus, SRNs are equivalent to finite-state automata.
[SRN characterization] Let INLINEFORM0 denote the languages acceptable by an SRN, and INLINEFORM1 the regular languages. Then, INLINEFORM2 
This characterization is quite diminished compared to Turing completeness. It is also more descriptive of what SRNs can express in practice. We will see that LSTMs, on the other hand, are strictly more powerful than the regular languages.
An LSTM is a recurrent network with a complex gating mechanism that determines how information from one time step is passed to the next. Originally, this gating mechanism was designed to remedy the vanishing gradient problem in SRNs, or, equivalently, to make it easier for the network to remember long-term dependencies BIBREF5 . Due to strong empirical performance on many language tasks, LSTMs have become a canonical model for NLP.
 BIBREF1 suggest that another advantage of the LSTM architecture is that it can use its cell state as counter memory. They point out that this constitutes a real difference between the LSTM and the GRU, whose update equations do not allow it to increment or decrement its memory units. We will further investigate this connection between LSTMs and counter machines.
[LSTM layer] ft = (Wf xt + Uf ht-1 + bf)
it = (Wi xt + Ui ht-1 + bi)
ot = (Wo xt + Uo ht-1 + bo)
ct = (Wc xt + Uc ht-1 + bc)
ct = ft ct-1 + it ct
ht = ot f(ct) .
In ( SECREF9 ), we set INLINEFORM0 to either the identity or INLINEFORM1 BIBREF1 , although INLINEFORM2 is more standard in practice. The vector INLINEFORM3 is the output that is received by the next layer, and INLINEFORM4 is an unexposed memory vector called the cell state.
[LSTM state complexity] The LSTM cell state INLINEFORM0 has state complexity INLINEFORM1 
At each time step INLINEFORM0 , we know that the configuration sets of INLINEFORM1 , INLINEFORM2 , and INLINEFORM3 are each subsets of INLINEFORM4 . Similarly, the configuration set of INLINEFORM5 is a subset of INLINEFORM6 . This allows us to rewrite the elementwise recurrent update as [ct]i = [ft]i [ct-1]i + [it]i [ct]i
= a [ct-1]i + b
where INLINEFORM0 and INLINEFORM1 .
Let INLINEFORM0 be the configuration set of INLINEFORM1 . At each time step, we have exactly two ways to produce a new value in INLINEFORM2 that was not in INLINEFORM3 : either we decrement the minimum value in INLINEFORM4 or increment the maximum value. It follows that |St| = 2 + |St-1|
|Sn| = O(n) .
For all INLINEFORM0 units of the cell state, we get DISPLAYFORM0 
The construction in thm:lstmmemorybound produces a counter machine whose counter and state update functions are linearly separable. Thus, we have an upper bound on the expressive power of the LSTM:
[LSTM upper bound] Let INLINEFORM0 be the real-time counter languages BIBREF6 , BIBREF7 . Then, INLINEFORM1 
thm:lstmupperbound constitutes a very tight upper bound on the expressiveness of LSTM computation. Asymptotically, LSTMs are not powerful enough to model even the deterministic context-free language INLINEFORM0 .
 BIBREF1 show how the LSTM can simulate a simplified variant of the counter machine. Combining these results, we see that the asymptotic expressiveness of the LSTM falls somewhere between the general and simplified counter languages. This suggests counting is a good way to understand the behavior of LSTMs.
The GRU is a popular gated recurrent architecture that is in many ways similar to the LSTM BIBREF8 . Rather than having separate forget and input gates, the GRU utilizes a single gate that controls both functions.
[GRU layer] zt = (Wz xt + Uz ht-1 + bz)
rt = (Wr xt + Ur ht-1 + br)
ut = ( Wu xt + Uu(rt ht-1) + bu )
ht = zt ht-1 + (1 - zt) ut .
 BIBREF1 observe that GRUs do not exhibit the same counter behavior as LSTMs on languages like INLINEFORM0 . As with the SRN, the GRU state is squashed between INLINEFORM1 and 1 ( SECREF11 ). Taken together, Lemmas SECREF10 and SECREF10 show that GRUs, like SRNs, are finite-state.
[GRU characterization] INLINEFORM0 
Synthesizing all of these results, we get the following complexity hierarchy: = L() = L()
L() .
Basic recurrent architectures have finite state, whereas the LSTM is strictly more powerful than a finite-state machine.
Attention is a popular enhancement to sequence-to-sequence (seq2seq) neural networks BIBREF9 , BIBREF10 , BIBREF11 . Attention allows a network to recall specific encoder states while trying to produce output. In the context of machine translation, this mechanism models the alignment between words in the source and target languages. More recent work has found that “attention is all you need” BIBREF12 , BIBREF13 . In other words, networks with only attention and no recurrent connections perform at the state of the art on many tasks.
An attention function maps a query vector and a sequence of paired key-value vectors to a weighted combination of the values. This lookup function is meant to retrieve the values whose keys resemble the query.
[Dot-product attention] For any INLINEFORM0 , define a query vector INLINEFORM1 , matrix of key vectors INLINEFORM2 , and matrix of value vectors INLINEFORM3 . Dot-product attention is given by INLINEFORM4 
In def:attention, INLINEFORM0 creates a vector of similarity scores between the query INLINEFORM1 and the key vectors in INLINEFORM2 . The output of attention is thus a weighted sum of the value vectors where the weight for each value represents its relevance.
In practice, the dot product INLINEFORM0 is often scaled by the square root of the length of the query vector BIBREF12 . However, this is only done to improve optimization and has no effect on expressiveness. Therefore, we consider the unscaled version.
In the asymptotic case, attention reduces to a weighted average of the values whose keys maximally resemble the query. This can be viewed as an INLINEFORM0 operation.
[Asymptotic attention] Let INLINEFORM0 be the subsequence of time steps that maximize INLINEFORM1 . Asymptotically, attention computes INLINEFORM2 
 [Asymptotic attention with unique maximum] If INLINEFORM0 has a unique maximum over INLINEFORM1 , then attention asymptotically computes INLINEFORM2 
Now, we analyze the effect of adding attention to an acceptor network. Because we are concerned with language acceptance instead of transduction, we consider a simplified seq2seq attention model where the output sequence has length 1:
[Attention layer] Let the hidden state INLINEFORM0 be the output of an encoder network where the union of the asymptotic configuration sets over all INLINEFORM1 is finite. We attend over INLINEFORM2 , the matrix stacking INLINEFORM3 , by computing INLINEFORM4 
In this model, INLINEFORM0 represents a summary of the relevant information in the prefix INLINEFORM1 . The query that is used to attend at time INLINEFORM2 is a simple linear transformation of INLINEFORM3 .
In addition to modeling alignment, attention improves a bounded-state model by providing additional memory. By converting the state of the network to a growing sequence INLINEFORM0 instead of a fixed length vector INLINEFORM1 , attention enables INLINEFORM2 state complexity.
[Encoder state complexity] The full state of the attention layer has state complexity INLINEFORM0 
The INLINEFORM0 complexity of the LSTM architecture means that it is impossible for LSTMs to copy or reverse long strings. The exponential state complexity provided by attention enables copying, which we can view as a simplified version of machine translation. Thus, it makes sense that attention is almost universal in machine translation architectures. The additional memory introduced by attention might also allow more complex hierarchical representations.
A natural follow-up question to thm:attentionstatecomplexity is whether this additional complexity is preserved in the attention summary vector INLINEFORM0 . Attending over INLINEFORM1 does not preserve exponential state complexity. Instead, we get an INLINEFORM2 summary of INLINEFORM3 .
[Summary state complexity] The attention summary vector has state complexity INLINEFORM0 
With minimal additional assumptions, we can show a more restrictive bound: namely, that the complexity of the summary vector is finite. sec:attentionresults discusses this in more detail.
While CNNs were originally developed for image processing BIBREF14 , they are also used to encode sequences. One popular application of this is to build character-level representations of words BIBREF15 . Another example is the capsule network architecture of BIBREF16 , which uses a convolutional layer as an initial feature extractor over a sentence.
[CNN acceptor] ht = ( Wh (xt-k .. xt+k) + bh )
h+ = maxpool(H)
p = (Wa h+ + ba) .
In this network, the INLINEFORM0 -convolutional layer ( SECREF5 ) produces a vector-valued sequence of outputs. This sequence is then collapsed to a fixed length by taking the maximum value of each filter over all the time steps ( SECREF5 ).
The CNN acceptor is much weaker than the LSTM. Since the vector INLINEFORM0 has finite state, we see that INLINEFORM1 . Moreover, simple regular languages like INLINEFORM2 are beyond the CNN thm:cnncounterexample. Thus, the subset relation is strict.
[CNN upper bound] INLINEFORM0 
So, to arrive at a characterization of CNNs, we should move to subregular languages. In particular, we consider the strictly local languages BIBREF17 .
[CNN lower bound] Let INLINEFORM0 be the strictly local languages. Then, INLINEFORM1 
Notably, strictly local formalisms have been proposed as a computational model for phonological grammar BIBREF18 . We might take this to explain why CNNs have been successful at modeling character-level information.
However, BIBREF18 suggest that a generalization to the tier-based strictly local languages is necessary to account for the full range of phonological phenomena. Tier-based strictly local grammars can target characters in a specific tier of the vocabulary (e.g. vowels) instead of applying to the full string. While a single convolutional layer cannot utilize tiers, it is conceivable that a more complex architecture with recurrent connections could.
In this section, we compare our theoretical characterizations for asymptotic networks to the empirical performance of trained neural networks with continuous logits.
The goal of this experiment is to evaluate which architectures have memory beyond finite state. We train a language model on INLINEFORM0 with INLINEFORM1 and test it on longer strings INLINEFORM2 . Predicting the INLINEFORM3 character correctly while maintaining good overall accuracy requires INLINEFORM4 states. The results reported in fig:countingresults demonstrate that all recurrent models, with only two hidden units, find a solution to this task that generalizes at least over this range of string lengths.
 BIBREF1 report failures in attempts to train SRNs and GRUs to accept counter languages, unlike what we have found. We conjecture that this stems not from the requisite memory, but instead from the different objective function we used. Our language modeling training objective is a robust and transferable learning target BIBREF19 , whereas sparse acceptance classification might be challenging to learn directly for long strings.
 BIBREF1 also observe that LSTMs use their memory as counters in a straightforwardly interpretable manner, whereas SRNs and GRUs do not do so in any obvious way. Despite this, our results show that SRNs and GRUs are nonetheless able to implement generalizable counter memory while processing strings of significant length. Because the strategies learned by these architectures are not asymptotically stable, however, their schemes for encoding counting are less interpretable.
In order to abstract away from asymptotically unstable representations, our next experiment investigates how adding noise to an RNN's activations impacts its ability to count. For the SRN and GRU, noise is added to INLINEFORM0 before computing INLINEFORM1 , and for the LSTM, noise is added to INLINEFORM2 . In either case, the noise is sampled from the distribution INLINEFORM3 .
The results reported in the right column of fig:countingresults show that the noisy SRN and GRU now fail to count, whereas the noisy LSTM remains successful. Thus, the asymptotic characterization of each architecture matches the capacity of a trained network when a small amount of noise is introduced.
From a practical perspective, training neural networks with Gaussian noise is one way of improving generalization by preventing overfitting BIBREF20 , BIBREF21 . From this point of view, asymptotic characterizations might be more descriptive of the generalization capacities of regularized neural networks of the sort necessary to learn the patterns in natural language data as opposed to the unregularized networks that are typically used to learn the patterns in carefully curated formal languages.
Another important formal language task for assessing network memory is string reversal. Reversing requires remembering a INLINEFORM0 prefix of characters, which implies INLINEFORM1 state complexity.
We frame reversing as a seq2seq transduction task, and compare the performance of an LSTM encoder-decoder architecture to the same architecture augmented with attention. We also report the results of BIBREF22 for a stack neural network (StackNN), another architecture with INLINEFORM0 state complexity (thm:stackstatecomplexity).
Following BIBREF22 , the models were trained on 800 random binary strings with length INLINEFORM0 and evaluated on strings with length INLINEFORM1 . As can be seen in table:extremereverse, the LSTM with attention achieves 100.0% validation accuracy, but fails to generalize to longer strings. In contrast, BIBREF22 report that a stack neural network can learn and generalize string reversal flawlessly. In both cases, it seems that having INLINEFORM2 state complexity enables better performance on this memory-demanding task. However, our seq2seq LSTMs appear to be biased against finding a strategy that generalizes to longer strings.
We have introduced asymptotic acceptance as a new way to characterize neural networks as automata of different sorts. It provides a useful and generalizable tool for building intuition about how a network works, as well as for comparing the formal properties of different architectures. Further, by combining asymptotic characterizations with existing results in mathematical linguistics, we can better assess the suitability of different architectures for the representation of natural language grammar.
We observe empirically, however, that this discrete analysis fails to fully characterize the range of behaviors expressible by neural networks. In particular, RNNs predicted to be finite-state solve a task that requires more than finite memory. On the other hand, introducing a small amount of noise into a network's activations seems to prevent it from implementing non-asymptotic strategies. Thus, asymptotic characterizations might be a good model for the types of generalizable strategies that noise-regularized neural networks trained on natural language data can learn.
Thank you to Dana Angluin and Robert Frank for their insightful advice and support on this project.
[Arbitary approximation] Let INLINEFORM0 be a neural sequence acceptor for INLINEFORM1 . For all INLINEFORM2 , there exist parameters INLINEFORM3 such that, for any string INLINEFORM4 with INLINEFORM5 , INLINEFORM6 
where INLINEFORM0 rounds to the nearest integer.
Consider a string INLINEFORM0 . By the definition of asymptotic acceptance, there exists some number INLINEFORM1 which is the smallest number such that, for all INLINEFORM2 , N(X) - 1L(X) < 12
 N(X) = 1L(X) . Now, let INLINEFORM0 be the set of sentences INLINEFORM1 with length less than INLINEFORM2 . Since INLINEFORM3 is finite, we pick INLINEFORM4 just by taking DISPLAYFORM0 
[General bound on state complexity] Let INLINEFORM0 be a neural network hidden state. For any length INLINEFORM1 , it holds that INLINEFORM2 
The number of configurations of INLINEFORM0 cannot be more than the number of distinct inputs to the network. By construction, each INLINEFORM1 is a one-hot vector over the alphabet INLINEFORM2 . Thus, the state complexity is bounded according to INLINEFORM3 
[SRN lower bound] INLINEFORM0 
We must show that any language acceptable by a finite-state machine is SRN-acceptable. We need to asymptotically compute a representation of the machine's state in INLINEFORM0 . We do this by storing all values of the following finite predicate at each time step: DISPLAYFORM0 
where INLINEFORM0 is true if the machine is in state INLINEFORM1 at time INLINEFORM2 .
Let INLINEFORM0 be the set of accepting states for the machine, and let INLINEFORM1 be the inverse transition relation. Assuming INLINEFORM2 asymptotically computes INLINEFORM3 , we can decide to accept or reject in the final layer according to the linearly separable disjunction DISPLAYFORM0 
We now show how to recurrently compute INLINEFORM0 at each time step. By rewriting INLINEFORM1 in terms of the previous INLINEFORM2 values, we get the following recurrence: DISPLAYFORM0 
Since this formula is linearly separable, we can compute it in a single neural network layer from INLINEFORM0 and INLINEFORM1 .
Finally, we consider the base case. We need to ensure that transitions out of the initial state work out correctly at the first time step. We do this by adding a new memory unit INLINEFORM0 to INLINEFORM1 which is always rewritten to have value 1. Thus, if INLINEFORM2 , we can be sure we are in the initial time step. For each transition out of the initial state, we add INLINEFORM3 as an additional term to get DISPLAYFORM0 
This equation is still linearly separable and guarantees that the initial step will be computed correctly.
These results follow similar arguments to those in section:srns and sec:srnproofs.
[GRU state complexity] The GRU hidden state has state complexity INLINEFORM0 
The configuration set of INLINEFORM0 is a subset of INLINEFORM1 . Thus, we have two possibilities for each value of INLINEFORM2 : either INLINEFORM3 or INLINEFORM4 . Furthermore, the configuration set of INLINEFORM5 is a subset of INLINEFORM6 . Let INLINEFORM7 be the configuration set of INLINEFORM8 . We can describe INLINEFORM9 according to S0 = { 0 }
St St-1 {-1, 1} .
This implies that, at most, there are only three possible values for each logit: INLINEFORM0 , 0, or 1. Thus, the state complexity of INLINEFORM1 is DISPLAYFORM0 
[GRU lower bound] INLINEFORM0 
We can simulate a finite-state machine using the INLINEFORM0 construction from thm:srnreduction. We compute values for the following predicate at each time step: DISPLAYFORM0 
Since ( EQREF27 ) is linearly separable, we can store INLINEFORM0 in our hidden state INLINEFORM1 and recurrently compute its update. The base case can be handled similarly to ( EQREF25 ). A final feedforward layer accepts or rejects according to ( EQREF23 ).
[thm:asymptoticattention restated] Let INLINEFORM0 be the subsequence of time steps that maximize INLINEFORM1 . Asymptotically, attention computes INLINEFORM2 
Observe that, asymptotically, INLINEFORM0 approaches a function DISPLAYFORM0 
Thus, the output of the attention mechanism reduces to the sum DISPLAYFORM0 
[thm:attentionstatecomplexity restated] The full state of the attention layer has state complexity INLINEFORM0 
By the general upper bound on state complexity thm:generalstatecomplexity, we know that INLINEFORM0 . We now show the lower bound.
We pick weights INLINEFORM0 in the encoder such that INLINEFORM1 . Thus, INLINEFORM2 for all INLINEFORM3 . Since the values at each time step are independent, we know that (Vn) = n
(Vn) = 2(n) .
[thm:summarycomplexity restated] The attention summary vector has state complexity INLINEFORM0 
By thm:asymptoticattention, we know that DISPLAYFORM0 
By construction, there is a finite set INLINEFORM0 containing all possible configurations of every INLINEFORM1 . We bound the number of configurations for each INLINEFORM2 by INLINEFORM3 to get DISPLAYFORM0 
[Attention state complexity lower bound] The attention summary vector has state complexity INLINEFORM0 
Consider the case where keys and values have dimension 1. Further, let the input strings come from a binary alphabet INLINEFORM0 . We pick parameters INLINEFORM1 in the encoder such that, for all INLINEFORM2 , DISPLAYFORM0 
and INLINEFORM0 . Then, attention returns DISPLAYFORM0 
where INLINEFORM0 is the number of INLINEFORM1 such that INLINEFORM2 . We can vary the input to produce INLINEFORM3 from 1 to INLINEFORM4 . Thus, we have (hn) = n
(hn) = (n) .
[Attention state complexity with unique maximum] If, for all INLINEFORM0 , there exists a unique INLINEFORM1 such that INLINEFORM2 , then INLINEFORM3 
If INLINEFORM0 has a unique maximum, then by cor:injectiveattention attention returns DISPLAYFORM0 
By construction, there is a finite set INLINEFORM0 which is a superset of the configuration set of INLINEFORM1 . Thus, DISPLAYFORM0 
[Attention state complexity with ReLU activations] If INLINEFORM0 for INLINEFORM1 , then INLINEFORM2 
By thm:asymptoticattention, we know that attention computes DISPLAYFORM0 
This sum evaluates to a vector in INLINEFORM0 , which means that DISPLAYFORM0 
thm:attentioninfinitevalues applies if the sequence INLINEFORM0 is computed as the output of INLINEFORM1 . A similar result holds if it is computed as the output of an unsquashed linear transformation.
[CNN counterexample] INLINEFORM0 
By contradiction. Assume we can write a network with window size INLINEFORM0 that accepts any string with exactly one INLINEFORM1 and reject any other string. Consider a string with two INLINEFORM2 s at indices INLINEFORM3 and INLINEFORM4 where INLINEFORM5 . Then, no column in the network receives both INLINEFORM6 and INLINEFORM7 as input. When we replace one INLINEFORM8 with an INLINEFORM9 , the value of INLINEFORM10 remains the same. Since the value of INLINEFORM11 ( SECREF5 ) fully determines acceptance, the network does not accept this new string. However, the string now contains exactly one INLINEFORM12 , so we reach a contradiction.
[Strictly INLINEFORM0 -local grammar] A strictly INLINEFORM1 -local grammar over an alphabet INLINEFORM2 is a set of allowable INLINEFORM3 -grams INLINEFORM4 . Each INLINEFORM5 takes the form INLINEFORM6 
where INLINEFORM0 is a padding symbol for the start and end of sentences.
[Strictly local acceptance] A strictly INLINEFORM0 -local grammar INLINEFORM1 accepts a string INLINEFORM2 if, at each index INLINEFORM3 , INLINEFORM4 
[Implies thm:convstrictlylocal] A INLINEFORM0 -CNN can asymptotically accept any strictly INLINEFORM1 -local language.
We construct a INLINEFORM0 -CNN to simulate a strictly INLINEFORM1 -local grammar. In the convolutional layer ( SECREF5 ), each filter identifies whether a particular invalid INLINEFORM2 -gram is matched. This condition is a conjunction of one-hot terms, so we use INLINEFORM3 to construct a linear transformation that comes out to 1 if a particular invalid sequence is matched, and INLINEFORM4 otherwise.
Next, the pooling layer ( SECREF5 ) collapses the filter values at each time step. A pooled filter will be 1 if the invalid sequence it detects was matched somewhere and INLINEFORM0 otherwise.
Finally, we decide acceptance ( SECREF5 ) by verifying that no invalid pattern was detected. To do this, we assign each filter a weight of INLINEFORM0 use a threshold of INLINEFORM1 where INLINEFORM2 is the number of invalid patterns. If any filter has value 1, then this sum will be negative. Otherwise, it will be INLINEFORM3 . Thus, asymptotic sigmoid will give us a correct acceptance decision.
Refer to BIBREF22 for a definition of the StackNN architecture. The architecture utilizes a differentiable data structure called a neural stack. We show that this data structure has INLINEFORM0 state complexity.
[Neural stack state complexity] Let INLINEFORM0 be a neural stack with a feedforward controller. Then, INLINEFORM1 
By the general state complexity bound thm:generalstatecomplexity, we know that INLINEFORM0 . We now show the lower bound.
The stack at time step INLINEFORM0 is a matrix INLINEFORM1 where the rows correspond to vectors that have been pushed during the previous time steps. We set the weights of the controller INLINEFORM2 such that, at each step, we pop with strength 0 and push INLINEFORM3 with strength 1. Then, we have (Sn) = n
(Sn) = 2(n) .

Figure and table captions:
Figure 1: With sigmoid activations, the network on the left accepts a sequence of bits if and only if xt = 1 for some t. On the right is the discrete computation graph that the network approaches asymptotically.
Table 1: Generalization performance of language models trained on anbnc. Each model has 2 hidden units.
Table 2: Max validation and generalization accuracies on string reversal over 10 trials. The top section shows our seq2seq LSTM with and without attention. The bottom reports the LSTM and StackNN results of Hao et al. (2018). Each LSTM has 10 hidden units.

Questions about this paper:
How do attention, recurrent and convolutional networks differ on the language classes they accept?

Answers:
Attention neural networks can represent more languages than other networks. Simple recurring networks can describe regular languages. CNNs can describe only strictly local languages.