On the Linguistic Capacity of Real-time Counter Automata
Authors: William Merrill
Venue:  (2020)
Keywords: formal language theory
counter automata
natural language processing
deep learning

Abstract: While counter machines have received little attention in theoretical computer science since the 1960s, they have recently achieved a newfound relevance to the field of natural language processing (NLP). Recent work has suggested that some strong-performing recurrent neural networks utilize their memory as counters. Thus, one potential way to understand the sucess of these networks is to revisit the theory of counter computation. Therefore, we choose to study the abilities of real-time counter machines as formal grammars. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, intersection, and many other common set operations. Next, we show that counter machines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neural network systems: successfully matching syntactic patterns does not guarantee that a counter-like model accurately represents underlying semantic structures. Finally, we consider the question of whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of particular interest for the interpretability of recurrent neural networks.

Under review as a conference paper at ICLR 2020
ON THE LINGUISTIC CAPACITY OF REAL-TIME COUNTER AUTOMATA
Anonymous authors Paper under double-blind review
ABSTRACT
While counter machines have received little attention in theoretical computer sci- ence since the 1960s, they have recently achieved a newfound relevance to the field of natural language processing (NLP). Recent work has suggested that some strong prongg-erorning recurrent neural networks utilize their memory as counters. Thus, one potential way understand the sucess of these networks is to revisit the theory of counter computation. Therefore, we choose to study the abilities of real- time counter machines as formal grammars. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, inter- section, and many other common set operations. Next, show that counter ma- chines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neu- ral network systems: successfully matching syntactic patterns does not guarantee that counter-like model accurately represents underlying semantic structures. Fi- nally, we consider the question of whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of particular interest for the interpretability of recurrent neural networks.
INTRODUCTION
is often taken for granted that modeling natural language syntax well requires a hierarchically structured grammar formalism. Early work in linguistics established that finite-state models are insufficient for describing the dependencies natural language data (Chomsky) (956). Instead, 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) (Hochreiter & Schmidhuber, 1997) have been shown perform well on tasks requiring structure sensitivity (Linzen al.) 2016)) though it is not obvious that such models have the capacity to represent hierarchical structure. This mismatch raises interesting questions for both linguists and practitioners of NLP. It is unclear what about the LSTM's structure lends 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 expressive capacity of LSTMs resembles that of counter ma- chines (Merrill 2019 Suzgun al. 2019) Weiss al. 2018 Weiss al. (2018) studied LSTMs with fully saturated weights (i.e. the activation functions evaluate to their asymptotic values instead of intermediate rational values) and showed that such models can express simplified counter lan- guages. MMrril] (019),, on the other hand, showed that the general counter languages are upper bound on the expressive capacity of saturated LSTMs. Thus, there seems be strong theoretical connection between LSTMs and the counter automata. Merrill (2019); Suzgun al. (2019); | Weiss cet al. (2018) also all report experimental results suggesting that some class of counter languages matches the learnable capacity of LSTMss trained by gradient descent.
Taking the counter machine as a simplified formal model of the LSTM, we study the formal prop- erties of counter machines grammars. We do this with the hope of understanding to what degree counter machines, and LSTMs by extension, have computational properties well-suited for repre- senting the structure of natural language. The contributions of this paper follows:

---

Under review as a conference paper at ICLR 2020
We prove that general counter machines, incremental counter machines, and stateless counter machines have equivalent expressive capacity, whereas simplified counter ma- chines (Weiss et al. 2018) strictly weaker than the general class.
We demonstrate that counter languages are closed under complement, union, intersection, and many other common operations.
We show that counter machines are incapable of representing the deep syntactic structure semantics of boolean expressions, even though they can validate whether boolean expression well-formed.
We prove that certain subclass of the counter languages are semilinear, and conjecture that this result holds for all counter languages.
2 DEFINITIONS
2.1 GENERAL COUNTER MACHINE
Informally, we can think of counter automata as finite-state automata that have been augmented by finite number of integer-valued counters. While processing string, the machine update the values of the counters, and the counters can turn inform the machine's state transitions.
Early results in theoretical computer science established that 2-counter machine with unbounded computation time is Turine-complete (Fischer 1966). However, restricting computation to be real- time (i.e. one iteration of computation per input) severely limits the counter machine's computational capacity (Fischer et al. 1968). A similar fact holds for recurrent neural networks like LSTMs (Weiss al. 2018). We study the capabilities of several types of real-time counter automata.
The first counter automaton we introduce is the general counter machine. This machine can ma- nipulate the counters by adding subtracting from them. The other variants that will go to define are special cases of this general machine.
For E Z. write +-m denote the function Ar. m. By x0, denote the constant function Ar.0.
Definition 2.1 (General counter machine). A k-counter machine is tuple (E, Q. 90. u, 6, F) with
1. A finite alphabet
A finite set states Q
3. An initial state go
4. A counter update function
u x - ((+m: m me 2) (x0))*
5. A state transition function
8: x x +Q
6. An acceptance mask
F F 10,
Given input string and counter machine, perform computation by processing x token at a time. For each token, we use to update the counters and ó to update the state according to the current input token, the current state, and finite mask of the current counter values. We formalize this in Definittion 2.2]
As preliminary remark on notation, we use 2(x) denote the zero check function
(<x) = { otherwise.
0 x =0
Given vector æ, use =(x) represent this function broadcasted over each element of the vector.
2

---

Under review as a conference paper at ICLR 2020
Definition 2.2 (Counter machine computation). Let (q. c) Q Zt be configuration of machine M. Upon reading input 2, E Σ, we define the transition
(g. c) > (5(x,, 9: z(c)), u( q (()))
Definition 2.3 (Real-time acceptance). For any string E E¹ with length n. a counter machine accepts if there exist states q1 ... 9n and counter configurations Ci. Cn such that
(00 0) + Ci) 722 ta., (An, Cn) E F.
Definition 2.4 (Real-time language acceptance). A counter machines accepts a language L if, for each z E Σ", it accepts x if and only if E L.
We denote the set of languages that are acceptable in real time by general counter machine as CL. We will use the terms "accept" and "decide" interchangeably. as accepting and deciding language equivalent for real-time automata.
2.2 COUNTER MACHINE VARIANTS
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 discussed by Weiss et al. (2018). The counter update function the simplified counter machine has two important constraints compared 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.
Definition 2.5 (Simplified counter machine). A counter machine is simplified if has the form
u - (-1, +0, +1, x0.
Another variant that we consider is the incremental counter machine. This machine also con- strained to have only increments and decrements on its counters, but the counter update function is allowed depend on the state and counter value.
Definition 2.6 (Incremental counter machine). An counter machine is incremental if has the form
Σ x Q 1)* (-1, +0, +1, x0)*
Finally, we define stateless variant of the counter machine. Removing state from the counter machine equivalent allowing to only have one state go. Definition 2.7 (Stateless counter machine). A counter machine is stateless
{go}-
COUNTER LANGUAGE HIERARCHY 3.1 SIMPLIFIED COUNTER LANGUAGES
Our first result relating counter classes is to show that the simplified counter languages are proper subset of the general counter languages. The weakness of the simplified machine that the update function is conditioned only by the input symbol. Thus, languages like a p2m2 which require switching counting behavior, cannot be decided correctly. We formalize this in Theorem 3.1
Theorem 3.1 (Weakness SCL). Let SCL be the set of languages acceptable real time by simplified counter machine. Then,
SCL C CL.
Proof. Consider the language "m2m This is trivially acceptable by 1-counter machine that adds 2 for each and subtracts for each b. On the other hand, shall show that it cannot be accepted by any simplified machine. Assume by way contradiction that such a simplified machine exists.

---

Under review as a conference paper at ICLR 2020
Tracking the ratio between a's and b's requires infinite state. Thus, the counters of M, opposed to the finite state, must encode whether 2m for strings of the form a'"b'. Let e be the value of some counter in M. We can decompose into the update contributed by a's and the the update contributed by l's as follows:
c = mil + Lub.
(2)
ua My E (,
(3)
Exhausting all the possible functions that c can compute, we get
E +m, +1, +m + 1), +m 1)]
(4)
=(c) E {0, m>0, 1ıs0, m+ m-tv0
(5)
We ignore the first four options for =()), as they clearly do not relate m to The final option checks whether the ratio is 1, not 2. Thus, (c) cannot distinguish whether 2m = L.
Note that this argument breaks down if we allow the counter update to depend on the state. In that case, we can build machine that has two counters and two states: Qo adds to the first counter while it reads 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, Yo transitions to qı which decrements the second counter. We accept if and only if both counters are 0 after En-
3.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 finite amount of overhead. This provides a reduction from general to incremental machines.
Theorem 3.2 (Generality of ICL). Let ICL be the set of languages acceptable in real time by an incremental counter machine. Then,
ICL = CL.
Proof. Let d be the maximum that is ever added or subtracted from a counter e in M. We simulate in M' using a counter d' and value q mod d encoded in finite state. We will implement "ring-counter" encoding of c such that
d'
lc/d]
mod d.
To simulate a x0 update on c, we apply x0 to c', and transition state such that q == 0.
To simulate +m update for some E Z, first change state such that q (g + m) mod d. Next, we apply the following update to c':
+1 if gf m d
if m < 0
(6)
+0 otherwise.
We can compute (c) by checking whether =(d') = 0 and q = 0.
3.3 STATELESS COUNTER LANGUAGES
Similarly, restricting counter machine be stateless does not weaken its expressive capacity. We show how to reduce an arbitrary stateful machine to 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.
Theorem 3.3 (Generality of QCL). Let QCL be the set of languages acceptable in real time by stateless counter machine. Then,
QCL -C.
4

---

Under review as a conference paper at ICLR 2020
Proof. We define stateless machine M' to simulate M by adding [Q]-Length vector of new counters called q'-
Let (i) denote the IQ -length one-hot vector encoding i, i.c. [w(t)] and all other indices Note that we consider w()) 0.
At initialization, q' encodes the initial state since q' invariant that, at any given time, q' = w(i) for some state Thus, the additional counters now encode the current state.
( Furthermore, define the
Let æ denote the concatenation of vectors a and y. We define the acceptance mask in M' as
F" (9o. bl bl)) (q. b) E F).
An analogous transformation allows to update the counters inherited from M. The last step is to properly update the new counters q' For each transition 6(2a, qs. b) = qj in M, we update o' by adding (i( w(). This ensures that the updated value of is one-hot since
(i) + ( wi)) + +w(()) =(j).
(8)
3.4 SUMMARY
The general counter machine, incremental counter machine, and stateless counter machine all con- verge the same linguistic capacity, which we call CL.
The simplified counter machine defined by Weiss et al. (2018), however, has a linguistic capacity SCL that is strictly weaker than CL.
4 COUNTER 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 limplies these closure properties, as well as many others.
Theorem 4.1 (General set operation closure). Let P be an m-ary operation over languages. If there exists an m-ary boolean function p such that
1 Pi (x) = pl ((LL, (x), I (x)),
then CL and SCL are both closed under P.
Proof. First, construct counter machines Mi..., Mn. that decide the counter languages Li..., Lm- We define a new machine M' that, on input æ, simulates Mi,.., Mn in parallel, and accepts if and only if
Let A be placeholder for either CL or SCL. Let L1, Le A. By Theorem 4.1 A is closed under the following operations:
E' L
(10)
L n La
(11)
L L2
(12)
L L2
(13)
(In T2) U (T2 Tn)-
(14)
5

---

return c= Under review as a conference paper at ICLR 2020
5 HIERARCHICAL EXPRESSIONS
We now study the ability of counter machines to represent the language T.m Definition 5.T). Like natural language, Lm has deep structure recursively composed from hierarchical constituents. Definition 5.1 (Lmi Fischer al., 1968). For any m, let Ln, be the language generated by:
<exp>
<VALUE>
<exp>
<UNARY>
<exp> <exp> <exp>
<exp>
<BINARY>
<exp>
AR-A <exp>
<exp>
Surprisingly, Fischer al, (9688) shows that, by implementing Algorithm I even 1-counter ma- chines can decide Lm in real time. Algorithm 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 <VALUE> as O, and the arity of an <m ARY> operation m.
Algorithm Deciding Lm (Fischer al. 1968)
1: procedure DECIDE(Z)
2: c+
3: for each 24 E do
4: C c+ ARITY (z,) -
5:
5.1 SEMANTIC EVALUATION STRUCTURE SENSITIVITY
While Algorithm decides Lms we observe that it is agnostic to the deep structure of the input in that it does not represent the dependencies between tokens. This means that it could not be used to evaluate these expressions, for example. Based on this observation, we prove that no counter machine can evaluate boolean expressions due to the deep structural sensitivity that semantic evalu- ation (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 L22 with values (0, 1} and binary operations (A, V}. We assign the following semanties to the terminals:
[0]
0
[1] =
(15)
[ Xpq. Pλq
(16)
M Apg. V q.
(17)
Furthermore, our semantics evaluates each nonterminal by applying the denotation of each syntactic
argument the semantic arguments of the operation. For example,
[v01] = [v[ [o], [1]) = 0 =
(18)
We also define semanties for non-constituent prefixes via function composition. For example,
[v]] M M Apgr. Vr..
(19)
Finally, we define the language as the set expressions x where [>] = under these semantics.
Theorem 5.1 (Weak evaluation). For any k. real-time k-counter machine cannot decide B.
Proof. Assume by way of contradiction that such an evaluation can be performed. We consider an input that contains prefix of operators followed by suffix of + values. For the machine to evaluate x correctly, the configuration after Tp must encode which boolean function Tp specifies.
However, a counter machine with counters only has O(p*) configurations after reading p charac- ters. We show by induction over p that p-length prefix of operators encode 2D boolean functions. Since the counter machine does not have enough configurations to encode all the possi- bilities, reach contradiction.

---

Under review as a conference paper at ICLR 2020
Base Case With p O, we have null prefix followed by one value that determines fore, we can represent exactly (2%) function, which is the identity.
[a]]
There-
Inductive Case The expression has prefix of operators #1:441 followed by values 2p+2:22+3- We decompose the semantics of the full expression to
[+] = [m]][ [22:2p+2], [[2p+a]))
(20)
Since [22:2p+2] has prefix of p operators, apply the inductive assumption show it can represent 2 2P boolean functions. Define / as the composition of [ri] with [22:2p+2]] There are two possible values for ʃ: fa. obtained when æ1 A, and ʃv. obtained when V. We complete the proof by verifying that fΛ and fv are necessarily different functions.
To do this, consider the minimal sequence of values that will satisfy them according a right-to-left ordering of the sequences. For fa, this minimal sequence ends in 1, whereas for fv it must end in Therefore, f can have unique values for each value of [22:20+2| Thus, a p 1-length sequence of prefixes can encode > 2 2P+1 boolean functions.
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 how CFGs can weakly generate Dutch center embedding (Pullum & Gazdar 1980), even though they cannot assign the correct cross-serial dependencies between subjects and verbs (Bresnan et 1982.
SEMILINEARITY
Semilinearity a condition that has been proposed as desired property for any formalism natural language syntax (Joshi et al. 1990). Intuitively, semilincarity ensures that the set of string lengths in a language is not unnaturally sparse. Regular, context-free. free, and a variety of mildly context-sensitivy languages are known to be semilinear (Joshi et al. 1990). The semilinearity of CL is an interesting open question if we aim understand the abilities counter machines as grammars.
6.1 DEFINITION
We first define semilinearity over sets of vectors before considering languages, To start, we introduce the notion linear set: Definition 6.1 (Linear set). A set S C Nk is linear if there exist W Nixm and b No such that
S (n N Wn + b b=
Semilinearity, then, is a weaker condition that specifies that a set is made up of a finite number of linear components: Definition 6.2 (Semilinear set), A set S C N is semilinear it is the finite union of linear sets.
To apply this definition to a language L, we translate each sentence (zr,, the Parikh mapping of z. The Parikh mapping of a sentence is, in more familiar machine learning terms. just its bag of tokens representation. For example, the Parikh mapping of abao with respect to Σ (a.b} is (3, 1). Definition 6.3 (Semilinear language). A language is semilinear (Vr()) | ar E L} semilinear.
L into vector by taking
6.2 SEMILINEARITY OF COUNTER LANGUAGES
While do not prove that the general counter languages semilinear, do prove it for dramatically restricted subclass of the counter languages. We define QSCL the set of language acceptable by a counter machine that is both simplified (aaiifiiiddDDiiittttoin (Definition 2.5) and stateless (Definition 2.7, and show that this class is indeed semilinear.

---

Under review as a conference paper at ICLR 2020
Theorem 6.1 (Semilinearity of QSCL). For all L E QSCL, L is semilinear.
Proof. We express L as
&
L U { c(x) = DEF
b) UVr (()) b.). bEF
(21)
Since semilinear languages are closed under finite union and intersection, the problem reduces to showing that (ar c2(x)) = b,} is semilinear. We apply the following trick:
{- (z) b,) = >" (b,
(22)
where Z is the set of all tokens that set counter to 0, and L(bb i) is the set of suffixes after the last occurence of some token in Z, for ever string in L. Since semilinear languages are closed under concatenation, and h and the finite language Z are trivially semilinear, we just need to show that L(b, i) is semilinear. Counter i cannot be set to zero on strings of L(b, i). so we can write
= G(x) = Σ (u(())) Σ (((o) u, (xx)
(23)
where # #x) is the number of occurrences of a in and u; denotes the vector of possible updates counter where each index corresponds to a different o E E. So, L(b, i) is the linear language
L(b.i) fo E E' u. (x) bq 0}.
(24)
Although the proof of Theorem 6.1 is nontrivial, it should noted that QSCL quite weak class. Such languages have limited ability to even detect the relative order of tokens in a string. We hope this argument might be extended show that SCL or CL semilinear.
CONCLUSION
We have shown that many variants of the counter machine converge to express the same class of formal languages, which supports that CL is robustly defined class. We also proved that real-time counter languages are closed under a large number of common set operations. This provides tools for future work investigating real-time counter automata.
We also showed that counter automata are incapable of evaluating boolean expressions, even though they capable of verifying that boolean expressions syntactically well-formed. This result has a clear parallel in the domain of natural language, where deciding whether sentence is grammatical different task than representing its deep syntactic or semantic structure. general take-away from our results is that just because counter machine (or LSTM) is sensitive to surface patterns in linguistic data does not mean can build correct semantic representations. Counter memory can be exploited to weakly match patterns in language, 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 linguis- tic capacity. We concluded only that a quite weak subclass the counter languages are semilinear, and encourage future work to address the general case.
REFERENCES
Joan Bresnan, Ronald M. Kaplan, Stanley Peters, and Annie Zaenen. Cross-serial dependencies in dutch. Linguistic Inquiry, 13(4)6613-635 1982. ISSN 00243892, 15309150. URL. http:
www. jstor.... wtt.:/..rgg/taaaee/eeeee...
Noam Chomsky. Three models for the description of language. IRE Transactions on information theory, 2(3):113-124 1956.
8

---

Under review as a conference paper at ICLR 2020
Patrick C Fischer. Turing machines with restricted memory access. Information and Control, 9(4):
364-379, 1966.
Patrick C. Fischer, Albert R. Meyer, and Armold L. Rosenberg. Counter machines and counter languages. Mathematical systems theory, 2(3):265-283, Sep 1968. ISSN 1433-0490. doi: 10. 1007/BF01694011
Sepp Hochreiter and Jrgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997. doi: 10. 19111//eco..999......1 URL
neco. 1997 9.8...8... 1735
Aravind K Joshi, K Vijay Shanker, and David Weir. The convergence of mildly context-sensitive grammar formalisms. Technical Reports (CIS), pp. 539, 1990.
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. Assessing the ability of LSTMs to learn syntax- sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521- 535, 2016. doi: 10.1162/tacl a 00115. URL https: /wwww wwwweb.wwwbb............ arghhhhooog///
Q16-1037
William Merrill. Sequential neural networks as automata. Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pp. 1-13, Florence, August 2019, As- sociation for Computational Linguistics. URL
W19-3900
Geoffrey K. Pullum and Gerald Gazdar. Natural languages and context-free languages. Linguistics and Philosophy, 4(4):471-504, 1980. doi: 10. O0.00///B00030000.
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. LSTM networks can perform dynamic counting. Proceedings of the Workshop on Deep Learning and Formal Lan- guages: Building Bridges, pp. 44 44-54, Florence, August 2019. Association for Computational Linguistics. UtLhttps:: / www. aclweb org/ htt.://....ggaatooooooooo/ooo//e
3905
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite pre- cision RNNs for language recognition. CoRR, abs/l abs//800500 805.04908 2018. URL http:://rxii>
arg/abs// 1805. 04908


Reviews:
[{"review_id": "SylMDPRYcr", "reviewer": "AnonReviewer6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\n\nThe authors investigate (subclasses of) generalized counter machines with respect to their weak generative capacity, their ability to represent structure, and several closure properties. This is motivated by recent indications that LSTMs have comparable expressivity to counter machines, so that the formal properties of these machines might provide indirect insights into the linguistic suitability of LSTMs.\n\n\nEvaluation\n----------\n\nI also reviewed this paper for SCiL a few months ago.\nWhile I had major reservations back then, I am happy to provide a more positive evaluation this time as the authors have done some revisions that clear up many points of confusion.\nI have to add two caveats, though.\nFirst, I am a bit disheartened that the authors chose not to adopt many of the excellent changes suggested by another SCiL reviewer (who went way beyond the call of duty with their multi-page review).\nSecond, I did not have sufficient time to check all proofs for their correctness.\nIn many cases the strategies strike me as intuitively sound, but my intuition tends to miss edge cases.\nNonetheless, I think that this paper, albeit a bit of a gamble, would make for an interesting addition to the program.\n\n\n1) Weakness: Link to neural networks still unclear\n\nThe central weakness of the paper is still the link between neural networks and counter automata.\nBased on what is said in the paper, this is merely a conjecture at this point, not a well-established fact. \nWithout this link, the value of the paper is unclear.\nIf, however, this conjecture should turn out to be true, the paper would mark a very strong starting point for further exploration.\nThis makes it a gamble worth taking.\n\n\n2) Strong results, but lack of examples\n\nThe results are not trivial and provide deep insights into the inner workings of counter machines.\nIn particular the fact that counter machines cannot correctly represent Boolean expressions reveals key limitations on their representational power.\nThe semilinearity result is less impressive because of how limited the machines are that it applies to, and I'm not sure that the proof provides a good basis for generalization to more complex machines.\nThe authors might consider removing this part to clear some space for examples, which are sorely needed.\nThe formalism is abstract and unfamiliar to most readers, and a few concrete examples would greatly strengthen the readers' intuition.\n\n\n3) No investigation of linguistically important string languages\n\nAs the authors make claims about linguistic adequacy, it is surprising that there is no discussion of TALs, MCFLs or PMCLFs.\nThe grammar formalism of GPSG was abandoned because it was limited to context-free languages and could not handle those more complex language classes.\nSo if counter machines fail here, the issue of their linguistic adequacy is already decided without further probing semilinearity or representational power.\nAs far as I can tell, real-time counter machines cannot generate the PMCLF a^{2^n}, which is an abstract model of unbounded copying constructions in natural language (see Radzisnky on Chinese number names, Michaelis & Kracht on Old Georgian case stacking, and Kobele on Yoruba).\nNor is it obvious to me that counter machines can handle the copy language {ww | w \\in \\Sigma^*}, a model of crossing dependencies, although they can handle a^n b^n c^n (a TAL).\nIt should also be possible to generate the linguistically undesirable MIX language, which is a 2-MCFL but not a TAL.\n\n\nMinor comments\n--------------\n\n- As noted in my SCiL review, your definitions still differ from those of Fischer et al. 1968. What is the reason for this?\n\n- Theorem 3.1: \\subsetneq would be clearer than \\subset\n\n- p4, typo: the the\n\n- Proof of Theorem 3.2: Unless I misunderstand your modulo construction, your ICL only has resolution up to mod n. For instance, with mod 2 it can distinguish 2 from 3, but not 2 from 4. The CL can do that. Don't you need a second counter c_i' for each c_i, then, to keep track of how often you have wrapped around modulo n in c_i? That would still be incremental as you can never wrap around by more than 1 in any given update.\n\n- Sec 6.1: in all those definitions, if should be iff\n\n\nReferences\n----------\n\n@ARTICLE{Radzinski91,\n  author = {Radzinski, Daniel},\n  title = {Chinese Number Names, Tree Adjoining Languages, and Mild Context\n\tSensitivity},\n  year = {1991},\n  journal = {Computational Linguistics},\n  volume = {17},\n  pages = {277--300},\n  url = {http://ucrel.lancs.ac.uk/acl/J/J91/J91-3002.pdf}\n}\n\n@INPROCEEDINGS{MichaelisKracht97,\n  author = {Michaelis, Jens and Kracht, Marcus},\n  title = {Semilinearity as a Syntactic Invariant},\n  year = {1997},\n  booktitle = {Logical Aspects of Computational Linguistics},\n  pages = {329--345},\n  editor = {Retor{\\'e}, Christian},\n  volume = {1328},\n  series = {Lecture Notes in Artifical Intelligence},\n  publisher = {Springer},\n  doi = {10.1007/BFb0052165},\n  url = {http://dx.doi.org/10.1007/BFb0052165}\n}\n\n@PHDTHESIS{Kobele06,\n  author = {Kobele, Gregory M.},\n  title = {Generating Copies: {A}n Investigation into Structural Identity in\n\tLanguage and Grammar},\n  year = {2006},\n  school = {UCLA},\n  url = {http://home.uchicago.edu/~gkobele/files/Kobele06GeneratingCopies.pdf}\n}", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1ll3f5JqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proof properties of counter machines that have in recent work be suggest that LSTMs can model those. \n\nThe papers starts to mentions related work that relates automaton's and counter machines with LSTMs. These related work papers do some correlational experiments partly restricted in size, layers and architecture. They provide mostly empirical evidence that some behaviour is related to performance seen in LSTMs, GRU, etc. and similar to those in counter automata. \n\nThe paper makes then the point to take  the counter machine as a simplified formal model of the LSTM. However, I would read Merrill 2019 that counter machines could be model via LSTMs but are not limited or they are not an upper bound what they can compute.  The authors does some proves on counter automata and hopes to gain insights into the properties of LSTMs used for NLP or semantic analysis and this would provide insights for the use in NLP.  It seems to me that the paper claims that counter automatons are an upper bound for the computation power of LSTMs. In the way I read this seems at least not well formulated or too strong.\n\nI would not follow the conclusion that 'A general take-away\nfrom our results is that just because a counter machine (or LSTM) is sensitive to surface patterns in\nlinguistic data does not mean it can build correct semantic representations'. \nThe argumentation is flawed as counter machines are not an upper limit of expressiveness of LSTMs nor do they describe well what they do. That one can use LSTMs to compute languages that counter automata can do too means not that they could do more. The property of Counter automata are useful for instance to build phrase structures meaning they can be use to express scope and keep track of. However, deeper layered networks are widely used to put structure over the scopes (arguments) to connected them in a higher order fashion.   \n\nThere are many paper which show empirical how to build semantic or syntactic structures using LSTMs - also in already quite well in seq2seq fashion. \n\nThe more theoretical part looks fine to me and could be of value to readers. Nevertheless, the authors could considere to revise  their claims as they are not well supported by the evidence provided in the paper nor pervious literature cited. \n\n   ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgskIy2YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Motivated by a link between LSTMs and counter machines (suggested by recent work, e.g. Merrill, 2019 et al.), this paper studies the formal properties of counter machines (and LSTMs by extension) as grammars, in hopes of discovering why LSTMs perform particularly well in language tasks despite having no obvious hierarchical structure.\n\nIt makes the following contributions. It shows that: (1) many variants of counter machine converge to the same formal language, (2) the counter languages are closed under common set operations (e.g. intersection, union, and complement), (3) counter machines are incapable of evaluating boolean expressions, and (4) only a weak subclass of CLs are sublinear (and most are not).\n\nWhile this paper gives thorough proofs, I would have liked to see more connection to practical NLP with some experiments. Also, I would have liked to see more concrete takeaways from this paper: if correctly detecting surface patterns doesn't mean that LSTMs build correct semantic representations, what can ensure that LSTMS do have a correct semantic representation? \n\nAs this paper is far from my area of expertise, I'm willing to change my score based on my co-reviewers.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an analysis of the languages that can be accepted by a counter machine, motivated by recent work that suggests that counter machines might be a good formal model from which to approach the analysis of LSTM representations.

This is one of the trickiest papers in my batch. Reviewers agree that it represents an interesting and provocative direction, and I suspect that it could yield valuable discussion at the conference. However, reviewers were not convinced that the claims made (or implied) _about LSTMs_ are motivated, given the imperfect analogy between them and counter machines. The authors promise some empirical evidence that might mitigate these concerns to some extent, but the paper has not yet been updated, so I cannot take that into account. 

As a very secondary point, which is only relevant because this paper is borderline, LSTMs are no longer widely used for language tasks, so discussion about the capacity of LSTMs _for language_ seems like an imperfect fit for an machine learning conference with a fairly applied bent.
Decision: Reject