On the Linguistic Capacity of Real-Time Counter Automata

Understand

Counter machines have achieved a newfound relevance to the field of natural language processing (NLP): recent work suggests some strong-performing recurrent neural networks utilize their memory as counters.

• Thus, one potential way to understand the success of these networks is to revisit the theory of counter computation.
• Therefore, we study the abilities of real-time counter machines as formal grammars, focusing on formal properties that are relevant for NLP models.
• We first show that several variants of the counter machine converge to express the same class of formal languages.