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 realtime 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.
Summary
-------
The 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.
Evaluation
----------
I also reviewed this paper for SCiL a few months ago.
While 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.
I have to add two caveats, though.
First, 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).
Second, I did not have sufficient time to check all proofs for their correctness.
In many cases the strategies strike me as intuitively sound, but my intuition tends to miss edge cases.
Nonetheless, I think that this paper, albeit a bit of a gamble, would make for an interesting addition to the program.
1) Weakness: Link to neural networks still unclear
The central weakness of the paper is still the link between neural networks and counter automata.
Based on what is said in the paper, this is merely a conjecture at this point, not a well-established fact. 
Without this link, the value of the paper is unclear.
If, however, this conjecture should turn out to be true, the paper would mark a very strong starting point for further exploration.
This makes it a gamble worth taking.
2) Strong results, but lack of examples
The results are not trivial and provide deep insights into the inner workings of counter machines.
In particular the fact that counter machines cannot correctly represent Boolean expressions reveals key limitations on their representational power.
The 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.
The authors might consider removing this part to clear some space for examples, which are sorely needed.
The formalism is abstract and unfamiliar to most readers, and a few concrete examples would greatly strengthen the readers' intuition.
3) No investigation of linguistically important string languages
As the authors make claims about linguistic adequacy, it is surprising that there is no discussion of TALs, MCFLs or PMCLFs.
The grammar formalism of GPSG was abandoned because it was limited to context-free languages and could not handle those more complex language classes.
So if counter machines fail here, the issue of their linguistic adequacy is already decided without further probing semilinearity or representational power.
As 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).
Nor 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).
It should also be possible to generate the linguistically undesirable MIX language, which is a 2-MCFL but not a TAL.
Minor comments
--------------
- As noted in my SCiL review, your definitions still differ from those of Fischer et al. 1968. What is the reason for this?
- Theorem 3.1: \subsetneq would be clearer than \subset
- p4, typo: the the
- 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.
- Sec 6.1: in all those definitions, if should be iff
References
----------
@ARTICLE{Radzinski91,
  author = {Radzinski, Daniel},
  title = {Chinese Number Names, Tree Adjoining Languages, and Mild Context
	Sensitivity},
  year = {1991},
  journal = {Computational Linguistics},
  volume = {17},
  pages = {277--300},
  url = {http://ucrel.lancs.ac.uk/acl/J/J91/J91-3002.pdf}
}
@INPROCEEDINGS{MichaelisKracht97,
  author = {Michaelis, Jens and Kracht, Marcus},
  title = {Semilinearity as a Syntactic Invariant},
  year = {1997},
  booktitle = {Logical Aspects of Computational Linguistics},
  pages = {329--345},
  editor = {Retor{\'e}, Christian},
  volume = {1328},
  series = {Lecture Notes in Artifical Intelligence},
  publisher = {Springer},
  doi = {10.1007/BFb0052165},
  url = {http://dx.doi.org/10.1007/BFb0052165}
}
@PHDTHESIS{Kobele06,
  author = {Kobele, Gregory M.},
  title = {Generating Copies: {A}n Investigation into Structural Identity in
	Language and Grammar},
  year = {2006},
  school = {UCLA},
  url = {http://home.uchicago.edu/~gkobele/files/Kobele06GeneratingCopies.pdf}
}