p7cs.FL

cs.FL

17 papers

The Illusion of State in State-Space Models

William Merrill, Jackson Petty, Ashish Sabharwal

2404.08819

Recurrent Neural Networks as Weighted Language Recognizers

Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, Kevin Knight

1711.05408

Succinct progress measures for solving parity games

Marcin Jurdzinski, Ranko Lazic

1702.05051

Transformers Learn Shortcuts to Automata

Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang

2210.10749

Inter-GPS: Interpretable Geometry Problem Solving with Formal Language and Symbolic Reasoning

Pan Lu, Ran Gong, Shibiao Jiang, Liang Qiu, Siyuan Huang, Xiaodan Liang, Song-Chun Zhu

2105.04165

On the Turing Completeness of Modern Neural Network Architectures

Jorge Pérez, Javier Marinković, Pablo Barceló

1901.03429

Tighter Bounds on the Expressivity of Transformer Encoders

David Chiang, Peter Cholak, Anand Pillay

2301.10743

A short proof of correctness of the quasi-polynomial time algorithm for parity games

Hugo Gimbert, Rasmus Ibsen-Jensen

1702.01953

Reachability Switching Games

John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani

1709.08991

MiniF2F: a cross-system benchmark for formal Olympiad-level mathematics

Kunhao Zheng, Jesse Michael Han, Stanislas Polu

2109.00110

Sequential Neural Networks as Automata

William Merrill

1906.01615

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, Pedro A. Ortega

2207.02098

A Formal Hierarchy of RNN Architectures

William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, Eran Yahav

2004.08500

LSTM Networks Can Perform Dynamic Counting

Mirac Suzgun, Sebastian Gehrmann, Yonatan Belinkov, Stuart M. Shieber

1906.03648

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Yiding Hao, Dana Angluin, Robert Frank

2204.06618

On the Linguistic Capacity of Real-Time Counter Automata

William Merrill

2004.06866

Theoretical Limitations of Self-Attention in Neural Sequence Models

Michael Hahn

1906.06755