Fetching the paper…
Reading the bibliography…
The recent successes and spread of large neural language models (LMs) call for a thorough understanding of their computational ability.
On the computational power of RNNs
Samuel A. Korsky and Robert C. Berwick. 2019 · 1906
Earlier work this paper cites.
Representation of events in nerve nets and finite automata
S. C. Kleene. 1956 · 1956
Earlier work this paper cites.
Syntactic Structures
Noam Chomsky. 1957 · 1957
Earlier work this paper cites.
Real time computation
Michael O. Rabin. 1963 · 1963
Earlier work this paper cites.
A new normal-form theorem for context-free phrase structure grammars
Sheila A. Greibach. 1965 · 1965
Earlier work this paper cites.
Language identification in the limit
E Mark Gold. 1967 · 1967
Earlier work this paper cites.
Real-time definable languages
Arnold L. Rosenberg. 1967 · 1967
Earlier work this paper cites.
Finite state automata and simple recurrent networks
Axel Cleeremans, David Servan-Schreiber, and James L. McClelland. 1989 · 1989
Earlier work this paper cites.
Approximation by superpositions of a sigmoidal function
G. Cybenko. 1989 · 1989
Earlier work this paper cites.
On the approximate realization of continuous mappings by neural networks
Ken-Ichi Funahashi. 1989 · 1989
Earlier work this paper cites.
Multilayer feedforward networks are universal approximators
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. 1989 · 1989
Earlier work this paper cites.
Finding structure in time
Jeffrey L. Elman. 1990 · 1990
Earlier work this paper cites.
Efficient simulation of finite automata by neural nets
Noga Alon, A. K. Dewdney, and Teunis J. Ott. 1991 · 1991
Earlier work this paper cites.
On the computational power of neural nets
Hava T. Siegelmann and Eduardo D. Sontag. 1992 · 1992
Earlier work this paper cites.
Cryptographic limitations on learning boolean formulae and finite automata
Michael Kearns and Leslie Valiant. 1994 · 1994
Earlier work this paper cites.
Optimal simulation of automata by neural nets
P. Indyk. 1995 · 1995
Earlier work this paper cites.
Long short-term memory
Sepp Hochreiter and Jürgen Schmidhuber. 1997 · 1997
Earlier work this paper cites.
Finite-state transducers in language and speech processing
Mehryar Mohri. 1997 · 1997
Earlier work this paper cites.
Relating probabilistic grammars and automata
Steven Abney, David McAllester, and Fernando Pereira. 1999 · 1999
Cited alongside, same era.
Approximation theory of the MLP model in neural networks
Allan Pinkus. 1999 · 1999
Cited alongside, same era.
On the determinization of weighted finite automata
Adam L. Buchsbaum, Raffaele Giancarlo, and Jeffery R. Westbrook. 2000 · 2000
Cited alongside, same era.
Efficient algorithms for testing the twins property
Cyril Allauzen and Mehryar Mohri. 2003 · 2003
Cited alongside, same era.
Convex Optimization
Stephen Boyd and Lieven Vandenberghe. 2004 · 2004
Cited alongside, same era.
A survey of neural networks and formal languages
Joshua Ackerman and George Cybenko. 2020 · 2006
Cited alongside, same era.
Breaking the softmax bottleneck: A high-rank RNN language model
Zhilin Yang, Zihang Dai, Ruslan Salakhutdinov, and William W. Cohen. 2018 · 2018
Later among the works it cites.
Universal function approximation by deep neural nets with bounded width and relu activations
Boris Hanin. 2019 · 2019
Later among the works it cites.
Sequential neural networks as automata
William Merrill. 2019 · 2019
Later among the works it cites.
Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchy
Thomas F. Icard. 2020 · 2020
Later among the works it cites.
A formal hierarchy of RNN architectures
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020 · 2020
Later among the works it cites.
Attention is Turing-complete
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. 2021 · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Introduction to Automata Theory, Languages, and Computation (3rd Edition)
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006 · 2006
Cited alongside, same era.
RNNs can generate bounded hierarchical languages with optimal memory
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning. 2020 · 2010
Cited alongside, same era.
Learning phrase representations using RNN encoder–decoder for statistical machine translation
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014b · 2014
Cited alongside, same era.
On the number of linear regions of deep neural networks
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. 2014 · 2014
Cited alongside, same era.
Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. 2014 · 2014
Cited alongside, same era.
Deep Learning
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016 · 2016
Cited alongside, same era.
Exploiting cloze-questions for few-shot text classification and natural language inference
Timo Schick and Hinrich Schütze. 2021 · 2021
Later among the works it cites.
FETA: A benchmark for few-sample task transfer in open-domain dialogue
Alon Albalak, Yi-Lin Tuan, Pegah Jandaghi, Connor Pryor, Luke Yoffe, Deepak Ramachandran, Lise Getoor, Jay Pujara, and William Yang Wang. 2022 · 2022
Later among the works it cites.
Softmax bottleneck makes language models unable to represent multi-mode word distributions
Haw-Shiuan Chang and Andrew McCallum. 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.
Extracting finite automata from RNNs using state merging
William Merrill and Nikolaos Tsilivis. 2022 · 2022
Later among the works it cites.
A measure-theoretic characterization of tight language models
Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Eisner, and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
On the representational capacity of recurrent neural language models
Franz Nowak, Anej Svete, Li Du, and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
Text classification via large language models
Xiaofei Sun, Xiaoya Li, Jiwei Li, Fei Wu, Shangwei Guo, Tianwei Zhang, and Guoyin Wang. 2023 · 2023
Later among the works it cites.
Recurrent neural language models as probabilistic finite-state automata
Anej Svete and Ryan Cotterell. 2023 · 2023
Later among the works it cites.
What languages are easy to language-model? a perspective from learning probabilistic regular languages
Nadav Borenstein, Anej Svete, Robin Shing Moon Chan, Josef Valvoda, Franz Nowak, Isabelle Augenstein, Eleanor Chodroff, and Ryan Cotterell. 2024 · 2024
Closest in time.
On the representational capacity of neural language models with chain-of-thought reasoning
Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. 2024 · 2024
Closest in time.
A theoretical result on the inductive bias of RNN language models
Anej Svete, Robin Shing Moon Chan, and Ryan Cotterell. 2024 · 2024
Closest in time.