pith. sign in

arxiv: 2509.07857 · v3 · submitted 2025-09-09 · 💻 cs.FL · cs.CC

Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems

Zeyu Chen , Junde Wu This is my paper

Pith reviewed 2026-05-18 17:57 UTC · model grok-4.3

classification 💻 cs.FL cs.CC
keywords affine automatarational transition matricesArthur-Merlin proof systemsnonregular languagesTuring-recognizable languagesATIMEPSPACEinteractive verification
0
0 comments X

The pith

Affine automata with rational transition matrices retain their full verification power in Arthur-Merlin proof systems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks whether the strong verification power of affine automata depends on arbitrary real numbers or holds when every transition matrix is restricted to rational entries. It answers by constructing both one-way and two-way rational affine automata that act as verifiers. These constructions verify benchmark nonregular languages one-way and, two-way, deliver weak verification of all Turing-recognizable languages, bounded-error strong verification of ATIME(2^O(n)) languages, and perfect-completeness strong verification of PSPACE languages. The results indicate that the verification advantages arise from the affine structure itself rather than from irrational parameters or infinite precision.

Core claim

Affine automata whose transition matrices have only rational entries can verify the same language classes as their real-valued counterparts in Arthur-Merlin proof systems. One-way rational affine verifiers handle nonregular languages that are hard for classical probabilistic models. Two-way rational affine verifiers weakly verify every Turing-recognizable language, provide strong bounded-error verification for every language in ATIME(2^{O(n)}), and give perfect-completeness strong verification for every language in PSPACE.

What carries the argument

Rational-valued affine transition matrices in one-way and two-way automata used as verifiers in Arthur-Merlin proof systems.

Load-bearing premise

Explicit constructions of rational transition matrices exist that preserve the required completeness and soundness for the targeted language classes.

What would settle it

A language in PSPACE (or ATIME(2^O(n))) for which no rational affine two-way verifier achieves the claimed perfect-completeness or bounded-error verification.

read the original abstract

Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur--Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in $\mathbf{ATIME}(2^{O(n)})$, and perfect-completeness strong verification for every language in $\mathbf{PSPACE}$. These results establish that the remarkable verification power of affine finite-state automata is structural.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims that restricting affine automata verifiers in Arthur-Merlin proof systems to rational-valued transition matrices preserves the model's verification power. At the one-way level, rational affine verifiers can handle benchmark nonregular languages that are hard or impossible for classical two-way probabilistic verifiers. At the two-way level, they achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in ATIME(2^{O(n)}), and strong verification with perfect completeness for every language in PSPACE. The central conclusion is that this verification power is structural to the affine mechanism rather than dependent on arbitrary real or irrational parameters.

Significance. If the explicit rational constructions hold, the result is significant because it isolates the affine linear-algebraic structure as the source of the enhanced verification capabilities, without reliance on infinite-precision or irrational entries. This strengthens comparisons to quantum models and provides a more concrete foundation for the model. The paper supplies explicit rational matrix constructions that maintain the required acceptance gaps and perfect completeness, so the stress-test concern about hidden irrational approximations in the two-way PSPACE case does not land.

minor comments (2)
  1. [§3] §3: The presentation of the one-way rational constructions for nonregular languages would be clearer with an explicit comparison table to the real-valued case from prior work.
  2. The notation for the two-way affine transition functions could be standardized across sections to avoid minor ambiguity in the matrix definitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive review and recommendation of minor revision. The report accurately summarizes the central claim that rational-valued affine verifiers retain the key verification advantages previously shown for real-valued affine automata.

Circularity Check

0 steps flagged

No circularity: new rational constructions are independent of prior fitted parameters

full rationale

The paper claims to supply explicit rational transition matrices that replicate the verification power previously shown for real-valued affine automata. No quoted step reduces a prediction to a fitted input, renames a known result, or loads the central claim on a self-citation whose content is itself defined by the present work. The one-way and two-way results are presented as following from the new rational constructions rather than from any self-definitional loop or imported uniqueness theorem. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the existence of rational matrix constructions that simulate the verification power of arbitrary real matrices; no free parameters or invented entities are mentioned, and the work relies on standard automata theory and linear algebra over the rationals.

axioms (1)
  • standard math Finite automata with affine transitions over the rationals can be composed and analyzed using standard linear-algebraic operations.
    Invoked when defining the rational model and its verification properties.

pith-pipeline@v0.9.0 · 5733 in / 1377 out tokens · 44673 ms · 2026-05-18T17:57:42.010880+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 1 internal anchor

  1. [1]

    IBM journal of research and development3(2), 114–125 (1959) https://doi.org/10.1147/rd.32

    Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM journal of research and development3(2), 114–125 (1959) https://doi.org/10.1147/rd.32. 0114

    work page doi:10.1147/rd.32 1959

  2. [2]

    Information and control6(3), 230–245 (1963) https://doi.org/10.1016/S0019-9958(63)90290-0

    Rabin, M.O.: Probabilistic automata. Information and control6(3), 230–245 (1963) https://doi.org/10.1016/S0019-9958(63)90290-0

    work page doi:10.1016/s0019-9958(63)90290-0 1963

  3. [3]

    [KNP07] Marta Kwiatkowska, Gethin Norman, and David Parker

    Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 66–75 (1997). https://doi.org/10.1109/SFCS.1997.646094 . IEEE

    work page doi:10.1109/sfcs.1997.646094 1997

  4. [4]

    The- oretical Computer Science237(1-2), 275–306 (2000) https://doi.org/10.1016/ S0304-3975(00)00042-5

    Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. The- oretical Computer Science237(1-2), 275–306 (2000) https://doi.org/10.1016/ S0304-3975(00)00042-5

    work page 2000

  5. [5]

    Theory of Computing Systems39, 165–188 (2006) https://doi.org/10.1007/s00224-005-1263-x 23

    Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Th´ erien, D.: Algebraic results on quantum automata. Theory of Computing Systems39, 165–188 (2006) https://doi.org/10.1007/s00224-005-1263-x 23

    work page doi:10.1007/s00224-005-1263-x 2006

  6. [6]

    Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classi- cal state. Theor. Comput. Sci.287(1), 299–311 (2002) https://doi.org/10.1016/ S0304-3975(02)00138-X

    work page 2002

  7. [7]

    In: Computer Science–Theory and Applications: 11th International Computer Sci- ence Symposium in Russia, CSR 2016, St

    D´ ıaz-Caro, A., Yakaryılmaz, A.: Affine computation and affine automaton. In: Computer Science–Theory and Applications: 11th International Computer Sci- ence Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings 11, pp. 146–160 (2016). https://doi.org/10.1007/978-3-319-34171-2 11 . Springer

    work page doi:10.1007/978-3-319-34171-2 2016

  8. [8]

    International Journal of Foundations of Computer Science 33(03n04), 349–370 (2022) https://doi.org/10.1142/S012905412241009X

    Nakanishi, M., Khadiev, K., Prusis, K., Vihrovs, J., Yakaryılmaz, A.: Exact affine counter automata. International Journal of Foundations of Computer Science 33(03n04), 349–370 (2022) https://doi.org/10.1142/S012905412241009X

    work page doi:10.1142/s012905412241009x 2022

  9. [9]

    International Journal of Foundations of Computer Science32(07), 827–847 (2021) https://doi.org/10.1142/S0129054121500246

    Ibrahimov, R., Khadiev, K., Pr¯ usis, K., Yakaryılmaz, A.: Error-free affine, uni- tary, and probabilistic obdds. International Journal of Foundations of Computer Science32(07), 827–847 (2021) https://doi.org/10.1142/S0129054121500246

    work page doi:10.1142/s0129054121500246 2021

  10. [10]

    In: Unconventional Computation and Natural Computation: 19th International Conference, UCNC 2021, Espoo, Finland, October 18–22, 2021, Proceedings 19, pp

    Khadieva, A., Yakaryılmaz, A.: Affine automata verifiers. In: Unconventional Computation and Natural Computation: 19th International Conference, UCNC 2021, Espoo, Finland, October 18–22, 2021, Proceedings 19, pp. 84–100 (2021). https://doi.org/10.1007/978-3-030-86880-0 5 . Springer

    work page doi:10.1007/978-3-030-86880-0 2021

  11. [11]

    arXiv preprint arXiv:2502.12879 (2025)

    Chen, Z., Yakaryılmaz, A.: Two-way affine automata can verify every language. arXiv preprint arXiv:2502.12879 (2025)

    work page arXiv 2025

  12. [12]

    In: Proceedings of the Seven- teenth Annual ACM Symposium on Theory of Computing, pp

    Babai, L.: Trading group theory for randomness. In: Proceedings of the Seven- teenth Annual ACM Symposium on Theory of Computing, pp. 421–429 (1985). https://doi.org/10.1145/22145.22192

    work page doi:10.1145/22145.22192 1985

  13. [13]

    Journal of the ACM (JACM)39(4), 800–828 (1992) https://doi.org/10.1145/ 146585.146605

    Dwork, C., Stockmeyer, L.: Finite state verifiers i: The power of interaction. Journal of the ACM (JACM)39(4), 800–828 (1992) https://doi.org/10.1145/ 146585.146605

    work page arXiv 1992

  14. [14]

    Quantum Information & Computation17(11-12), 1027–1043 (2017) https://doi.org/10.26421/QIC17.11-12-6

    Say, A.C., Yakaryilmaz, A.: Magic coins are useful for small-space quantum machines. Quantum Information & Computation17(11-12), 1027–1043 (2017) https://doi.org/10.26421/QIC17.11-12-6

    work page doi:10.26421/qic17.11-12-6 2017

  15. [15]

    Cengage Learning, United States of America (2013)

    Sipser, M.: Introduction to the Theory of Computation, 3rd Edition. Cengage Learning, United States of America (2013)

    work page 2013

  16. [16]

    Com- plexity Theory: Current Research, pp

    Condon, A.: The complexity of space bounded interactive proof systems. Com- plexity Theory: Current Research, pp. 147–190. Cambridge University Press, (1993)

    work page 1993

  17. [17]

    Chandra and Dexter C

    Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Journal of the ACM (JACM)28(1), 114–133 (1981) https://doi.org/10.1145/322234.322243 24

    work page doi:10.1145/322234.322243 1981

  18. [18]

    SIAM Journal on Computing19(6), 1011–1023 (1990) https://doi.org/10.1137/0219069

    Dwork, C., Stockmeyer, L.J.: A time complexity gap for two-way probabilis- tic finite-state automata. SIAM Journal on Computing19(6), 1011–1023 (1990) https://doi.org/10.1137/0219069

    work page doi:10.1137/0219069 1990

  19. [19]

    Information and Computation241, 145–166 (2015) https://doi.org/10.1016/j.ic.2015.02.003

    Zheng, S., Qiu, D., Gruska, J.: Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata. Information and Computation241, 145–166 (2015) https://doi.org/10.1016/j.ic.2015.02.003

    work page doi:10.1016/j.ic.2015.02.003 2015

  20. [20]

    In: FOCS, vol

    Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs. In: FOCS, vol. 89, pp. 462–467 (1989). https://doi.org/10.1109/SFCS.1989.63519 . Citeseer

    work page doi:10.1109/sfcs.1989.63519 1989

  21. [21]

    In: The Proceedings of Workshop on Quantum and Classical Complexity, pp

    Yakaryılmaz, A.: Public qubits versus private coins. In: The Proceedings of Workshop on Quantum and Classical Complexity, pp. 45–60 (2013). Citeseer

    work page 2013

  22. [22]

    Journal of computer and system sciences29(2), 274–301 (1984) https://doi.org/10.1016/ 0022-0000(84)90034-5

    Reif, J.H.: The complexity of two-player games of incomplete information. Journal of computer and system sciences29(2), 274–301 (1984) https://doi.org/10.1016/ 0022-0000(84)90034-5

    work page 1984

  23. [23]

    Journal of Computer and System Sciences36(3), 452–489 (1988) https://doi.org/10.1016/0022-0000(88) 90050-3

    Condon, A., Ladner, R.E.: Probabilistic game automata. Journal of Computer and System Sciences36(3), 452–489 (1988) https://doi.org/10.1016/0022-0000(88) 90050-3

    work page doi:10.1016/0022-0000(88 1988

  24. [24]

    Lucchesi

    Yakaryılmaz, A.: QIP⊆AM(2QCFA) (2025). https://doi.org/10.48550/arXiv. 2508.21020 25

    work page internal anchor Pith review doi:10.48550/arxiv 2025