Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages Andy Y ang University of Notre Dame David Chiang University of Notre Dame Dana Angluin Y ale University

Oct-9-2025, 19:01:24 GMT–Neural Information Processing Systems 

A key technique in these proofs is the use of B-RASP, which, like RASP (Weiss et al., 2021), is a small programming language that compiles into transformers.