Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

Language models are few-shot learners

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020 · 1901

Earlier work this paper cites.

On finite monoids having only trivial subgroups

M. P. Schützenberger. 1965 · 1965

Earlier work this paper cites.

Tense Logic and the Theory of Linear Order

Johan Anthony Willem Kamp. 1968 · 1968

Earlier work this paper cites.

Counter-Free Automata

Robert McNaughton and Seymour Papert. 1971 · 1971

Earlier work this paper cites.

On the temporal analysis of fairness

Dov Gabbay, Amir Pnueli, Saharon Shelah, and Jonathan Stavi. 1980 · 1980

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.

Regular languages in 𝑁𝐶 1 \mathit{NC^{1}}

David A. Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. 1992 · 1992

Earlier work this paper cites.

Stutter-invariant temporal properties are expressible without the next-time operator

Doron Peled and Thomas Wilke. 1997 · 1997

Earlier work this paper cites.

An until hierarchy and other applications of an Ehrenfeucht–Fraïssé game for temporal logic

Kousha Etessami and Thomas Wilke. 2000 · 2000

Earlier work this paper cites.

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, and Denis Thérien. 2005 · 2005

Earlier work this paper cites.

On the Krohn-Rhodes cascaded decomposition theorem

Oded Maler. 2010 · 2010

Earlier work this paper cites.

Layer normalization

Original

Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 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

Cited alongside, same era.

BERT: Pre-training of deep bidirectional Transformers for language understanding

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019 · 2019

Cited alongside, same era.

On the ability and limitations of Transformers to recognize formal languages

Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020 · 2020

Cited alongside, same era.

How can self-attention networks recognize Dyck-n languages?

Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. 2020 · 2020

Cited alongside, same era.

Theoretical limitations of self-attention in neural sequence models

Michael Hahn. 2020 · 2020

Cited alongside, same era.

Two-Stream Transformer Architecture With Discrete Attention for Better Interpretrability and Separation of Model Concerns

Overcoming a theoretical limitation of self-attention

David Chiang and Peter Cholak. 2022 · 2022

Later among the works it cites.

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.

In-context learning and induction heads

Original

Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. 2022 · 2022

Later among the works it cites.

Tighter bounds on the expressivity of transformer encoders

David Chiang, Peter Cholak, and Anand Pillay. 2023 · 2023

Closest in time.

Learning Transformer programs

Dan Friedman, Alexander Wettig, and Danqi Chen. 2023 · 2023

Closest in time.