Partial Answer of How Transformers Learn Automata

2025/04/29 by Tiantian Zhang, Zhang, Tiantian
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning (cs.LG) #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2504.20395

openalex publication_date 2025/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a novel framework for simulating finite automata using representation-theoretic semidirect products and Fourier modules, achieving more efficient Transformer-based implementations.

Related

• The Role of Logic and Automata in Understanding Transformers
• Transformers Learn Shortcuts to Automata
• Automata Extraction from Transformers
• Simulating Weighted Automata over Sequences and Trees with Transformers
• Extracting Moore Machines from Transformers using Queries and Counterexamples