2025/02/18 by Zeyu Chen, Chen, Zeyu, Abuzer Yakaryılmaz +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2502.12879
openalex publication_date 2025/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
When used as verifiers in Arthur-Merlin systems, two-way quantum finite automata can verify membership in all languages with bounded error with double-exponential expected running time, which cannot be achieved by their classical counterparts. We obtain the same result for affine automata with single-exponential expected time. We show that every binary (and r-ary) language is verified by some two-way affine finite automata verifiers by presenting two protocols: A weak verification protocol uses a single affine register and the input is read once; and, a strong verification protocol uses two affine registers. These results reflects the remarkable verification capabilities of affine finite automata.