The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective Chris Köcher RPTU Kaiserslautern-Landau

Formal language theory has recently been successfully employed to unravel the power of transformer encoders. This setting is primarily applicable in Natural Language Processing (NLP), as a token embedding function (where a bounded number of tokens is admitted) is first applied before feeding the input to the transformer.