Dana Angluin

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and at…