Fetching the paper…
Reading the bibliography…
Synthetic datasets constructed from formal languages allow fine-grained examination of the learning and generalization capabilities of machine learning systems for sequence classification.
A logical calculus of the ideas immanent in nervous activity
Warren S McCulloch and Walter Pitts · 1943
Earlier work this paper cites.
Three models for the description of language
Noam Chomsky · 1956
Earlier work this paper cites.
Representation of events in nerve nets and finite automata
S.C. Kleene · 1956
Earlier work this paper cites.
Syntactic Structures
Noam Chomsky · 1957
Earlier work this paper cites.
Finite automata and their decision problems
Michael O. Rabin and Dana Scott · 1959
Earlier work this paper cites.
Weak second-order arithmetic and finite automata
J. Richard Büchi · 1960
Earlier work this paper cites.
Aspects of the theory of syntax
Noam Chomsky · 1965
Earlier work this paper cites.
Implicit learning of artificial grammars
Arthur S. Reber · 1967
Earlier work this paper cites.
Counter-Free Automata
Robert McNaughton and Seymour Papert · 1971
Earlier work this paper cites.
Piecewise testable events
Imre Simon · 1975
Earlier work this paper cites.
Classifying regular events in symbolic logic
Wolfgang Thomas · 1982
Earlier work this paper cites.
Learning of construction of finite automata from examples using hill-climbing. RR: Regular set recognizer
Masaru Tomita · 1982
Earlier work this paper cites.
Encoding sequential structure: experience with the real-time recurrent learning algorithm
Andrew W. Smith and David Zipser · 1989
Earlier work this paper cites.
The induction of dynamical recognizers
Jordan B. Pollack · 1991
Earlier work this paper cites.
Learning and extracting finite state automata with second-order recurrent neural networks
C.L. Giles, C.B. Miller, D. Chen, H.H. Chen, G.Z. Sun, and Y.C. Lee · 1992
Earlier work this paper cites.
Induction of finite-state automata using second-order recurrent networks
Raymond L. Watrous and G.M. Kuhn · 1992
Earlier work this paper cites.
Learning long-term dependencies with gradient descent is difficult
Y. Bengio, P. Simard, and P. Frasconi · 1994
Earlier work this paper cites.
Discrete recurrent neural networks for grammatical inference
Zheng Zeng, R.M. Goodman, and P. Smyth · 1994
Earlier work this paper cites.
The dynamics of discrete-time computation with application to recurrent neural networks and finite state machine extraction
Mike Casey · 1996
Earlier work this paper cites.
Languages, automata, and logic
Wolfgang Thomas · 1997
Earlier work this paper cites.
A Mathematical Introduction to Logic
Herbert B. Enderton · 2001
Earlier work this paper cites.
Learning nonregular languages: A comparison of simple recurrent networks and LSTM
J. Schmidhuber, F. Gers, and D. Eck · 2002
Cited alongside, same era.
Incremental training of first order recurrent neural networks to predict a context-sensitive language
Stephan K. Chalup and Alan D. Blair · 2003
Cited alongside, same era.
Kalman filters improve LSTM network performance in problems unsolvable by traditional recurrent nets
Juan Antonio Pérez-Ortiz, Felix A. Gers, Douglas Eck, and Jürgen Schmidhuber · 2003
Cited alongside, same era.
A First Course in Logic
Shawn Hedman · 2004
Cited alongside, same era.
Elements of Finite Model Theory
Leonid Libkin · 2004
Cited alongside, same era.
Statistical comparisons of classifiers over multiple data sets
Janez Demšar · 2006
Cited alongside, same era.
Closing brackets with recurrent neural networks
Natalia Skachkova, Thomas Trost, and Dietrich Klakow · 2018
Later among the works it cites.
Evaluating and comparing classifiers: Review, some recommendations and limitations
Katarzyna Stąpor · 2018
Later among the works it cites.
Extracting automata from recurrent neural networks using queries and counterexamples
Gail Weiss, Yoav Goldberg, and Eran Yahav · 2018
Later among the works it cites.
Some classes of sets of structures definable without quantifiers
James Rogers and Dakotah Lambert · 2019
Later among the works it cites.
On the ability and limitations of transformers to recognize formal languages
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal · 2020
Later among the works it cites.
How can self-attention networks recognize Dyck-n languages?
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
OpenFst: A general and efficient weighted finite-state transducer library
Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri · 2007
Cited alongside, same era.
On languages piecewise testable in the strict sense
James Rogers, Jeffrey Heinz, Gil Bailey, Matt Edlefsen, Molly Visscher, David Wellcome, and Sean Wibel · 2010
Cited alongside, same era.
Tier-based strictly local constraints for phonology
Jeffrey Heinz, Chetan Rawal, and Herbert G. Tanner · 2011
Cited alongside, same era.
Aural pattern recognition experiments and the subregular hierarchy
James Rogers and Geoffrey K. Pullum · 2011
Cited alongside, same era.
What complexity differences reveal about domains in language
Jeffrey Heinz and William Idsardi · 2013
Cited alongside, same era.
Cognitive and sub-regular complexity
James Rogers, Jeffrey Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel · 2013
Cited alongside, same era.
Later among the works it cites.
Finite-State Text Processing
Kyle Gorman and Richard Sproat · 2021
Later among the works it cites.
Sensitivity as a Complexity Measure for Sequence Classification Tasks
Michael Hahn, Dan Jurafsky, and Richard Futrell · 2021
Later among the works it cites.
Typology emerges from simplicity in representations and learning
Dakotah Lambert, Jonathan Rawski, and Jeffrey Heinz · 2021
Later among the works it cites.
Handbook of Automata Theory , volume 1
Jean-Éric Pin, editor · 2021
Later among the works it cites.
Unifying Classification Schemes for Languages and Processes With Attention to Locality and Relativizations Thereof
Dakotah Lambert · 2022
Later among the works it cites.
Simplicity bias in transformers and their ability to learn sparse Boolean functions
Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom · 2023
Closest in time.
Neural networks and the Chomsky hierarchy
Gregoire 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
Closest in time.
Relativized adjacency
Dakotah Lambert · 2023
Closest in time.
Formal languages and the NLP black box
William Merrill · 2023
Closest in time.
A logic for expressing log-precision transformers
William Merrill and Ashish Sabharwal · 2023
Closest in time.
System description: A theorem-prover for subregular systems: The Language Toolkit and its interpreter, plebby
Dakotah Lambert · 2024
Closest in time.
Connecting weighted automata, tensor networks and recurrent neural networks through spectral learning
Tianyu Li, Doina Precup, and Guillaume Rabusseau · 2024
Closest in time.
What formal languages can transformers express? A survey, 2024
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin · 2024
Closest in time.
Masked hard-attention transformers recognize exactly the star-free languages, 2024
Andy Yang, David Chiang, and Dana Angluin · 2024
Closest in time.