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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yang, Andy, Chiang, David, Angluin, Dana
Format:	Preprint
Published:	2023
Subjects:	Formal Languages and Automata Theory Machine Learning Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Simulating Hard Attention Using Soft Attention
by: Yang, Andy, et al.
Published: (2024)

What Formal Languages Can Transformers Express? A Survey
by: Strobl, Lena, et al.
Published: (2023)

Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
by: Yang, Andy, et al.
Published: (2024)

Length Generalization Bounds for Transformers
by: Yang, Andy, et al.
Published: (2026)

Transformers as Transducers
by: Strobl, Lena, et al.
Published: (2024)

Transformers are Inherently Succinct
by: Bergsträßer, Pascal, et al.
Published: (2025)

Softmax Transformers are Turing-Complete
by: Jiang, Hongjian, et al.
Published: (2025)

Synthesis and Verification of Transformer Programs (Technical Report)
by: Jiang, Hongjian, et al.
Published: (2026)

Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
by: Angluin, Dana, et al.
Published: (2022)

RNN Generalization to Omega-Regular Languages
by: Pert, Charles, et al.
Published: (2025)

Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
by: Mandrioli, Dino, et al.
Published: (2020)

The Role of Logic and Automata in Understanding Transformers
by: Lin, Anthony W., et al.
Published: (2025)

Random Graph Generation in Context-Free Graph Languages
by: Vastarini, Federico, et al.
Published: (2024)

Inferring Symbolic Automata
by: Fisman, Dana, et al.
Published: (2021)

Model-Free Learning of Safe yet Effective Controllers
by: Bozkurt, Alper Kamil, et al.
Published: (2021)

On the Expressiveness of State Space Models via Temporal Logics
by: Alsmann, Eric, et al.
Published: (2026)

Learning Quantitative Automata Modulo Theories
by: Hsiung, Eric, et al.
Published: (2024)

Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
by: Iosif, Radu, et al.
Published: (2023)

Algebraic Closure of Matrix Sets Recognized by 1-VASS
by: Manssour, Rida Ait El, et al.
Published: (2025)

Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
by: Zhang, Yuanrui, et al.
Published: (2023)

Logic and Languages of Higher-Dimensional Automata
by: Amrane, Amazigh, et al.
Published: (2024)

Half-Positional Objectives Recognized by Deterministic Büchi Automata
by: Bouyer, Patricia, et al.
Published: (2022)

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
by: Czerwiński, Wojciech, et al.
Published: (2025)

Characterization and Decidability of FC-Definable Regular Languages
by: Thompson, Sam M., et al.
Published: (2025)

A Uniform Framework for Language Inclusion Problems
by: Doveri, Kyveli, et al.
Published: (2024)

Algebraic Characterizations of Classes of Regular Languages in DynFO
by: Barloy, Corentin, et al.
Published: (2026)

Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
by: Czerwiński, Wojciech, et al.
Published: (2022)

A Practical Specification Language for Automatic Quantum Program Verification (Technical Report)
by: Tsai, Wei-Lun, et al.
Published: (2026)

Automatic Generation of Safety-compliant Linear Temporal Logic via Large Language Model: A Self-supervised Framework
by: Li, Junle, et al.
Published: (2025)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
by: Daviaud, Laure, et al.
Published: (2023)

Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
by: Jecker, Ismaël, et al.
Published: (2023)

A Direct Translation from LTL with Past to Deterministic Rabin Automata
by: Azzopardi, Shaun, et al.
Published: (2024)

Improved Algorithm for Reachability in $d$-VASS
by: Fu, Yuxi, et al.
Published: (2024)

Lemur: Integrating Large Language Models in Automated Program Verification
by: Wu, Haoze, et al.
Published: (2023)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
by: Rooduijn, Jan, et al.
Published: (2024)

A proof theory of right-linear (omega-)grammars via cyclic proofs
by: Das, Anupam, et al.
Published: (2024)

The Alternation Hierarchy of First-Order Logic on Words is Decidable
by: Barloy, Corentin, et al.
Published: (2025)

Positive First-order Logic on Words and Graphs
by: Kuperberg, Denis
Published: (2022)

An algebraic theory of ω-regular languages, via μν-expressions
by: Das, Anupam, et al.
Published: (2025)

Function spaces for orbit-finite sets
by: Bojańczyk, Mikołaj, et al.
Published: (2024)