Transformers as Transducers

On finite monoids having only trivial subgroups

Marcel Paul Schützenberger. 1965 · 1965

Earlier work this paper cites.

Counter-free Automata

R. McNaughton and S. Papert. 1971 · 1971

Earlier work this paper cites.

Parity, circuits, and the polynomial-time hierarchy

Merrick Furst, James B. Saxe, and Michael Sipser. 1984 · 1984

Earlier work this paper cites.

Finite-state transducers in language and speech processing

Mehryar Mohri. 1997 · 1997

Earlier work this paper cites.

Harmony, Dominance, and Control

Eric Bakovic. 2000 · 2000

Earlier work this paper cites.

Computational approaches to morphology and syntax

Brian Roark and Richard Sproat. 2007 · 2007

Earlier work this paper cites.

Aperiodic two-way transducers and FO-transductions

Olivier Carton and Luc Dartois. 2015 · 2015

Earlier work this paper cites.

First-order definability of rational transductions: An algebraic approach

Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote. 2016 · 2016

Earlier work this paper cites.

Attention is all you need

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017 · 2017

Earlier work this paper cites.

Polyregular functions

Original

Mikołaj Bojańczyk. 2018 · 2018

Earlier work this paper cites.

Single-use automata and transducers for infinite alphabets

Mikołaj Bojańczyk and Rafal Stefański. 2020 · 2020

Cited alongside, same era.

Theoretical limitations of self-attention in neural sequence models

Michael Hahn. 2020 · 2020

Cited alongside, same era.

Implicit automata in typed λ \lambda -calculi I: aperiodicity in a non-commutative logic

Cécilia Pradic and Lê Thành Dũng Nguyễn. 2020 · 2020

Cited alongside, same era.

Two-way transducers with planar behaviours are aperiodic

Lê Thành Dũng Nguyễn. 2021 · 2021

Cited alongside, same era.

Attention is Turing-complete

Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021 · 2021

Cited alongside, same era.

Thinking like transformers

Gail Weiss, Yoav Goldberg, and Eran Yahav. 2021 · 2021

Cited alongside, same era.

Formal language recognition by hard attention Transformers: Perspectives from circuit complexity

Yiding Hao, Dana Angluin, and Robert Frank. 2022 · 2022

Later among the works it cites.

Saturated transformers are constant-depth threshold circuits

William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022 · 2022

Later among the works it cites.

Neural networks and the Chomsky hierarchy

Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023 · 2023

Later among the works it cites.

Two-way automata and transducers with planar behaviours are aperiodic

Original

Lê Thành Dũng Nguyễn, Camille Noûs, and Cécilia Pradic. 2023 · 2023

Later among the works it cites.

Challenging BIG-bench tasks and whether chain-of-thought can solve them

Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc Le, Ed Chi, Denny Zhou, and Jason Wei. 2023 · 2023

Later among the works it cites.