What Formal Languages Can Transformers Express? A Survey

Lena Strobl, William Merrill, Gail Weiss, David Chiang, Dana Angluin
11/1/2023
cs.LGcs.CLcs.FL

No confident code implementation found for this paper.

Abstract

As transformers have gained prominence in natural language processing, some researchers have investigated theoretically what problems they can and cannot solve, by treating problems as formal languages. Exploring such questions can help clarify the power of transformers relative to other models of computation, their fundamental capabilities and limits, and the impact of architectural choices. Work in this subarea has made considerable progress in recent years. Here, we undertake a comprehensive survey of this work, documenting the diverse assumptions that underlie different results and providing a unified framework for harmonizing seemingly contradictory findings.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Why transformers are obviously good models of language

89% match2024

AlgoFormer: An Efficient Transformer Framework with Algorithmic Structures

89% match1 repo12024

Introduction to Transformers: an NLP Perspective

87% match1 repo532023

A Comparative Study on Code Generation with Transformers

87% match2024

On the Universality of Transformer Architectures; How Much Attention Is Enough?

86% match2025

Transformers in Speech Processing: A Survey

85% match2023

Cite this paper

@article{strobl2023what,
  title  = {What Formal Languages Can Transformers Express? A Survey},
  author = {Lena Strobl and William Merrill and Gail Weiss and David Chiang and Dana Angluin},
  year   = {2023},
  eprint = {2311.00208},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2311.00208v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2311.00208.svg)](https://codeofpaper.com/paper/2311.00208)

Discussion