2 citations · 4 across the 8 of their papers we have counts for
3 papers · 1 filter
Transformers are Inherently Succinct
Pascal Bergsträßer, Ryan Cotterell, Anthony W. Lin
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 c…
The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
Pascal Bergsträßer, Chris Köcher, Anthony Widjaja Lin +1
Formal language theory has recently been successfully employed to unravel the power of transformer encoders. This setting is primarily applicable in Natural Language Processing (NL…
Revisiting Membership Problems in Subclasses of Rational Relations
Pascal Bergsträßer, Moses Ganardi
We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The…