Natural Computing Computer Science Applications

Two-way affine automata can verify every language

Chen, Zeyu, Yakaryılmaz, Abuzer
Springer Nature · 2026-09-16 · DOI 10.1007/s11047-026-10088-3

Abstract

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 an analogous result for affine automata with single-exponential expected time. Using the equivalent nondeterministic formulation adopted throughout the paper, we investigate the language recognition power of two-way affine nondeterministic automata under weak and strong bounded-error criteria. We show that every language over every fixed finite alphabet can be weakly or strongly recognized with bounded error by suitable two-way affine nondeterministic automata, via two protocols: a weak protocol uses a single affine register and reads the input once, and a strong protocol uses two affine registers. These results reflect the remarkable capabilities of affine finite automata in this setting.

Read at publisher →