Transformers Are Inherently Succinct
Bergsträßer; Pascal; Cotterell; Ryan; Lin; Anthony W
Computer Science > Formal Languages and Automata Theory
Title:Transformers are Inherently Succinct
View PDF HTML (experimental)Abstract:We propose succinctness as a measure of the expressive power of a transformer in describing a concept. To this end, we prove that transformers are highly expressive in that they can represent formal languages substantially more succinctly than standard representations of formal languages like finite automata and Linear Temporal Logic (LTL) formulas. As a...