Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers

Andy Yang, David Chiang

Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for bett…