Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Yiding Hao, Dana Angluin, Robert Frank

This paper analyzes three formal models of Transformer encoders that differ in the form of their self-attention mechanism: unique hard attention (UHAT); generalized unique hard att…