On the Linguistic Capacity of Real-Time Counter Automata

Introduction

It is often taken for granted that modeling natural language syntax well requires a grammar formalism sensitive to compositional structure. Early work in linguistics established that finite-state models are insufficient for describing the dependencies in natural language data . Instead, a formalism capable of expressing the relations in terms of hierarchical constituents ought to be necessary.

Recent advances in deep learning and NLP, however, challenge this long-held belief. Neural network formalisms like the long short-term memory network (LSTM) perform fairly well on tasks requiring structure sensitivity , even though it is not obvious that they have the capacity or bias to represent hierarchy. This mismatch raises interesting questions for both linguists and practitioners of NLP. It is unclear what about the LSTM architecture might lend itself towards good linguistic representations, and under what conditions these representations might fall short of grasping the structure and meaning of language.

Recent work has suggested that the practical learnable capacity of LSTMs resembles that of counter machines . Theoretically, this connection is motivated by studying the “saturated” version of the LSTM network, i.e. replacing each continuous activation function with a step function. Under these conditions, the LSTM reduces to a discrete automaton that uses its memory cell as integer-valued counter registers. define a simplified class of counter languages that falls within the expressive capacity of this saturated LSTM model. On the other hand, a more general class of counter languages is an upper bound on the expressive capacity of saturated LSTMs . Thus, there is a strong theoretical connection between LSTMs and counter automata.

Furthermore, these theoretical results for saturated LSTMs seem to predict what classes of formal languages LSTMs can empirically learn. show how LSTMs learn to model languages like $a^{n}b^{n}$ by using their memory to count $n$, whereas other recurrent neural network architectures without saturated counting abilities fail. Similarly, shows how LSTMs cannot reverse strings, just like real-time counter automata . Further, LSTMs can flawlessly model $1$-Dyck strings by using their memory to count , but, like counter automata, they cannot model $2$-Dyck . It seems that, where LSTMs succeed at algorithmic tasks, they do so by counting, and where they fail, their failure might be explained by their inability to reliably implement more complex types of memory.

Inspired by the connection of LSTMs to counter automata, we study the formal properties of counter machines as language recognizers. We do this with the hope of understanding the abilities of counter-structured memory, and to what degree it has computational properties well-suited for representing compositional structure. The contributions of this paper are as follows:

We prove that several interesting counter machine variants converge to the same linguistic capacity, whereas simplified counter machines are strictly weaker than classical counter machines.

We demonstrate that counter languages are closed under complement, union, intersection, and many other common operations.

We show counter machines cannot evaluate compositional boolean expressions, even though they can check whether such expressions are well-formed.

We prove that a certain subclass of the counter languages are semilinear, and conjecture that this result holds for all counter languages.

Definitions

Informally, we can think of counter automata as finite-state automata that have been augmented by a finite number of integer-valued counters. While processing a string, the machine can update the values of the counters, and the counters can in turn inform the machine’s state transitions.

Early results in theoretical computer science established that a $2$-counter machine with unbounded computation time is Turing-complete . However, restricting computation to be real-time (i.e. one iteration of computation per input) severely limits the counter machine’s computational capacity . A similar fact holds for recurrent neural networks like LSTMs . We study the language recognition abilities of several types of real-time counter automata.

A $k$-counter machine is a tuple $\langle\Sigma,Q,q_{0},u,\delta,F\rangle$ with

A finite set of states $Q$The original definition distinguishes between “autonomous” and “polling” states, a distinction that is vacuous in the real-time case we are studying.

A machine processes an input string $x$ one token at a time. For each token, we use $u$ to update the counters and $\delta$ to update the state according to the current input token, the current state, and a finite mask of the current counter values. We formalize this in 2.

For a vector $\mathbf{v}$, let $z(\mathbf{v})$ to denote the broadcasted “zero-check” function, i.e.

For any string $x\in\Sigma^{*}$ with length $n$, a counter machine accepts $x$ if there exist states $q_{1},..,q_{n}$ and counter configurations $\mathbf{c}_{1},..,\mathbf{c}_{n}$ such that

A counter machines accepts a language $L$ if, for each $x\in\Sigma^{*}$, it accepts $x$ iff $x\in L$.

2 Restricted Counter Machines

Now, we can can consider various restrictions of the general counter machine, and the corresponding classes of languages acceptable by such automata.

First, we present the simplified counter machine . The counter update function in the simplified counter machine has two important constraints compared to the general machine. First, it can only be conditioned by the input symbol at each time step. Second, it can only increment or decrement its counters instead of being able to add or subtract arbitrary constants.

A counter machine is simplified if $u$ has the form

Another variant that we consider is the incremental counter machine. The arguments to the update function of this machine are not restricted, but the additive operations are constrained to ${\pm}1$.

An counter machine is incremental if $u$ has the form

Finally, we define a stateless variant of the counter machine. Removing state from the counter machine is equivalent to allowing it to only have one state $q_{0}$.

A counter machine is stateless if $Q=\{q_{0}\}$.

3 Saturated LSTMs

We say the LSTM accepts iff $y_{t}=1$. In practice, (7) is often $\mathbf{o}_{t}\odot\tanh(\mathbf{c}_{t})$. We remove the $\tanh$ for clarity, as its monotonicity does not change the expressiveness of the saturated network. These equations specify a discrete automaton that is highly similar to a counter machine .

The major difference between the saturated LSTM and the classical counter machines is that the LSTM partitions the counter values by passing them through a linear map and applying a thresholding function, whereas the classical counter machines probes whether or not the counters are zero. For example, for a counter $c$, the saturated LSTM could test $c\leq 5$, whereas the general counter machine can only test $c=0$. Motivated by this, we define the threshold counter machine, which views its counters by thresholding them instead of testing equality to .

Counter Language Hierarchy

Our first result relating counter classes is to show that the simplified counter languages are a proper subset of the general counter languages. The weakness of the simplified machine is that the update function is conditioned only by the input symbol. Thus, languages like $a^{m}b^{2m}$, which require switching counting behavior, cannot be decided correctly. We formalize this in Theorem 3.1.

Consider the language $a^{m}b^{2m}$. This is trivially acceptable by a 1-counter machine that adds 2 for each $a$ and subtracts 1 for each $b$. On the other hand, we shall show that it cannot be accepted by any simplified machine. Assume by way of contradiction that such a simplified machine $M$ exists. We assume without loss of generality that $M$ does not apply a ${\times}0$ update, as doing so would erase all information about the prefix.

Tracking the ratio between $a$’s and $b$’s requires infinite state. Thus, the counters of $M$, as opposed to the finite state, must encode whether $2m=l$ for strings of the form $a^{m}b^{l}$. Let $c$ be the value of some counter in $M$. We can decompose $c$ into the update contributed by $a$’s and the the update contributed by $b$’s:

Exhausting all the possible functions that $c$ can compute, we get

We ignore the first four options for $z(c)$, as they do not relate $m$ to $l$. The final option tests $m/l=1$, not $2$. Thus, $z(c)$ cannot test whether $2m=l$.

Note that this argument breaks down if the counter update can depend on the state. In that case, we can build a machine that has two counters and two states: $q_{0}$ adds 1 to the first counter while it reads $a$, and then decrements the first counter and increments the second counter when it reads $b$. When the first counter is empty and the second counter is not empty, $q_{0}$ transitions to $q_{1}$, which decrements the second counter. We accept iff both counters are after $x_{n}$.

2 Incremental Counter Languages

Unlike the simplified counter machine, the incremental machine has the same linguistic capacity as the general machine. We can simulate each counter on a general machine with a finite amount of overhead. This provides a reduction from general to incremental machines.

We can compute $z(c)$ by checking whether $z(c^{\prime})=0$ and $q=0$.

3 Stateless Counter Languages

Similarly, restricting a counter machine to be stateless does not weaken its expressive capacity. We show how to reduce an arbitrary stateful machine to a stateless machine that has been augmented with additional counters. The key idea here is that we can use the additional counters as a one-hot vector that tracks the state of the original machine.

We define a new stateless machine $M^{\prime}$ to simulate $M$ by adding a $|Q|$-length vector of counters called $\mathbf{q}^{\prime}$. Let $\mathbf{\omega}(i)$ denote the $\left\lvert Q\right\rvert$-length one-hot vector encoding $i$, i.e. $[\mathbf{\omega}(i)]_{i}=1$, and all other indices are . We consider $\mathbf{\omega}(0)=\mathbf{0}$.

At initialization, $\mathbf{q}^{\prime}$ encodes the initial state since $\mathbf{q}^{\prime}=\mathbf{0}=\mathbf{\omega}(0)$. Furthermore, we define the invariant that, at any given time, $\mathbf{q}^{\prime}=\mathbf{\omega}(i)$ for some state $i$. Thus, the additional counters now encode the current state.

Let $\mathbf{x}\|\mathbf{y}$ denote the concatenation of vectors $\mathbf{x}$ and $\mathbf{y}$. We define the new acceptance mask in $M^{\prime}$ as

We can update the counters inherited from $M$ analogously to (14). The last step is to properly update the state counters $\mathbf{q}^{\prime}$. For each transition $\delta(x_{t},q_{i},\mathbf{b})=q_{j}$ in $M$, we update $\mathbf{q}^{\prime}$ by adding $-\mathbf{\omega}(i)+\mathbf{\omega}(j)$. This ensures $\mathbf{q}^{\prime}$ is correct since

4 Threshold Counter Languages

We show that the threshold counter languages are equivalent to the general counter languages. As thresholding is a key capability of the saturated LSTM formalism, this suggests that much of the LSTM capacity falls within the general counter languages, although it does not provably establish containment.

Assume without loss of generality that only one threshold check $m$ applies to each counter $c$ (we can create copies of a counter and distribute the threshold checks over them if this is not the case), and that $m>0$. We implement a ring-counter construction similar to the one used in Theorem 3.2, representing $c$ with a new counter $c^{\prime}=\lfloor c/m\rfloor$ and finite-state component $q=c\mod m$. We also store the sign of $c$ in finite state by recording whenever both $c^{\prime}$ and $q$ pass zero. Having all this information, we conclude $c\leq m$ iff the sign is negative or $c^{\prime}=0$.

The construction in Theorem 3.4 can be directly adapted to show that a general counter machine can simulate checking ${=}m$ in addition to ${=}0$.

5 Summary

Closure Properties

Another way to understand the counter languages is through their closure properties. It turns out that the real-time counter languages are closed under a wide array of common operations, including complement, intersection, union, set difference, and symmetric set difference. The general result in Theorem 4.1 implies these closure properties, as well as many others.

Let $P$ be an $m$-ary operation over languages. If there exists an $m$-ary boolean function $p$ such that

First, we construct counter machines $M_{1},..,M_{m}$ that decide the counter languages $L_{1},..,L_{m}$. We define a new machine $M^{\prime}$ that, on input $x$, simulates $M_{1},..,M_{m}$ in parallel, and accepts if and only if

Compositional Expressions

We now study the abilities of counter machines on the language $L_{m}$ (9). Like natural language, $L_{m}$ has a deep structure consisting of recursively nested hierarchical constituents.

For any $m$, let $L_{m}$ be the language generated by:

Surprisingly, even a $1$-counter machines can decide $L_{m}$ in real time by implementing Algorithm 1 . Algorithm 1 uses a counter to keep track of the depth at any given index. If the depth counter reaches $-1$ at the end of the string, the machine has verified that the string is well-formed. We define the arity of a as , and the arity of an operation as $m$.

While Algorithm 1 decides $L_{m}$, it is agnostic to the deep structure of the input in that it does not represent the hierarchical dependencies between tokens. This means that it could not be used to evaluate these expressions. Based on this observation, we prove that no counter machine can evaluate boolean expressions due to the deep structural sensitivity that semantic evaluation (as opposed to syntactic acceptance) requires. We view boolean evaluation as a simpler formal analogy to evaluating the compositional semantics of natural language.

To be more formal, consider an instance of $L_{2}$ with values $\{0,1\}$ and binary operations $\{\wedge,\vee\}$. We assign the following semantics to the terminals:

Our semantics evaluates each nonterminal by applying the denotation of each syntactic argument to the semantic arguments of the operation. For example:

We also define semantics for non-constituent prefixes via function composition:

We define the language $B$ as the set of valid strings $x$ where \mbox{[\![=]\!]}1.

Assume by way of contradiction that there exists a counter machine deciding $B$. We consider an input $x$ that contains a prefix of $p$ operators followed by a suffix of $p+1$ values. For the machine to evaluate $x$ correctly, the configuration after $x_{p}$ must encode which boolean function $x_{p}$ specifies.

However, a counter machine with $k$ counters only has $O(p^{k})$ configurations after reading $p$ characters. We show by induction over $p$ that an $p$-length prefix of operators can encode $\geq 2^{p}$ boolean functions. Since the machine does not have enough configurations to encode all the possibilities, we reach a contradiction.

With $p=0$, we have a null prefix followed by one value that determines [​].Wecanrepresentexactly1(2^0)function,whichistheidentity. Inductive Case. The expression has a prefix of operators x:1+p1 followed by values x:+p2+2p3. We decompose the semantics of the full expression to

Since [​]hasaprefixofpoperators,weapplytheinductiveassumptiontoshowitcanrepresent ≥2^pbooleanfunctions.Definefasthecompositionof [​]with [​].Therearetwopossiblevaluesforf:f_∧,obtainedwhenx_1 = ∧,andf_∨,obtainedwhenx_1 = ∨.Wecompletetheproofbyverifyingthatf_∧andf_∨arenecessarilydifferentfunctions.Todothis,-considertheminimalsequenceofvaluesthatwillsatisfythemaccordingtoarighttoleftorderingofthesequences.Forf_∧,thisminimalsequenceendsin1,whereasforf_∨itmustendina0.Therefore,frepresentsatleasttwouniquefunctionsforeachvalueof [​].Thus,ap+1-lengthsequenceofprefixescanencode≥2 ⋅2^p = 2^p+1booleanfunctions. Theorem 5.1 shows how counter machines cannot represent certain hierarchical dependencies, even when the generated language is within the counter machine’s weak expressive capacity. This is analogous to how CFGs can weakly generate Dutch center embedding , even though they cannot assign the correct cross-serial dependencies between subjects and verbs . Thus, while counter memory can track certain formal properties of compositional languages, it cannot represent the underlying hierarchical structure in a deep way. 6 Semilinearity Semilinearity is a condition that has been proposed as a desired property for any formalism of natural language syntax . Intuitively, semilinearity ensures that the set of string lengths in a language is not unnaturally sparse. Regular, context-free, and a variety of mildly context-sensitive languages are known to be semilinear . The semilinearity of CL is an interesting open question for understanding the abilities of counter machines as grammars.

We first define semilinearity over sets of vectors before considering languages. To start, we introduce the notion of a linear set:

A set ⊆SNk is linear if there exist ∈WN×km and ∈bNk such that

Semilinearity, then, is a weaker condition that specifies that a set is made up of a finite number of linear components:

A set ⊆SNk is semilinear if it is the finite union of linear sets.

To apply this definition to a language L, we translate each string ∈xL into a vector by taking Ψ(x), the Parikh mapping of x. The Parikh mapping of a sentence is its “bag of tokens” representation. For example, the Parikh mapping of abaa with respect to =Σ{a,b} is ⟨3,1⟩. We say that a language L is semilinear if its image under Ψ, i.e. {Ψ(x)∣∈xL}, is semilinear.

2 Semilinearity of Counter Languages

We do not prove that the general counter languages are semilinear, but we do prove it for a dramatically restricted subclass of the counter languages. Define ~QSCL as the set of language acceptable by a counter machine that is both simplified (5) and stateless (7). ~QSCL is indeed semilinear.

Applying the definition of counter machine acceptance, we express L as

Semilinear languages are closed under finite union and intersection, so we just need to show {x|=ci(x)bi} is semilinear. We apply the following trick:

where Zi is the set of all tokens that set counter i to 0, and Li is the set of suffixes after the last occurence of some token in Zi. Since semilinear languages are closed under concatenation, and Σ∗ and the finite language Zi are trivially semilinear, we just need to show that Li is semilinear. Counter i cannot be set to zero on strings of Li, so we can write

where ui denotes the vector of possible updates to counter i where each index corresponds to a different ∈σΣ. So, Li is the linear language

Although the proof of Theorem 6.1 is nontrivial, ~QSCL is a weak class. Such languages have limited ability to even detect the relative order of tokens in a string. We hope the proof might be extended to show SCL or CL is semilinear.

We have shown that many variants of the counter machine converge to express the same class of formal languages, which supports that CL is a robustly defined class. The variations we explored move the classical general counter machine closer to the LSTM in form without changing its expressive power. We also proved real-time counter languages are closed under a large number of common set operations, providing tools for future work investigating counter automata.

We also showed that counter automata are incapable of evaluating boolean expressions, even though they are capable of verifying that boolean expressions are syntactically well-formed. This result has a clear parallel in the domain of natural language: deciding whether a sentence is grammatical is different than building a sentence’s correct compositional meaning. A general take-away from our results is that just because a counter machine (or LSTM) is sensitive to surface patterns in language does not mean it can build correct semantic representations. Counter memory can be exploited to weakly match patterns in linguistic data, which might provide the wrong kinds of inductive bias for achieving sophisticated natural language understanding.

Finally, we asked whether counter languages are semilinear as another way of studying their power. We concluded that a weak subclass of the counter languages are semilinear, and encourage future work to address the general case.

Thanks to Dana Angluin, Robert Frank, Yiding Hao, Roy Schwartz, and Yoav Goldberg, as well as other members of Computational Linguistics at Yale and the Allen Institute for AI, for their suggestions on various versions of this work. Additional thanks to several anonymous reviewers for their exceptional feedback.