Transformers are Inherently Succinct

TL;DR

We study succinctness as a measure of the expressive power of transformers. Succinctness---how compactly a formalism can describe a language relative to other formalisms---is a classical notion in logic and automata theory.

Opening excerpt from the authors’ abstract. source