6533b828fe1ef96bd1288da2

RESEARCH PRODUCT

Affine Automata Verifiers

Aliya KhadievaAliya KhadievaAbuzer Yakaryilmaz

subject

Discrete mathematicsFinite-state machineUnary operationComputer scienceUnary languageSubset sum problemAffine transformationUpper and lower boundsNPAutomaton

description

We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted to have only integer-valued or rational-valued transitions. We observe that rational-valued verifiers can be simulated by integer-valued verifiers, and their protocols can be simulated in nondeterministic polynomial time. We show that this upper bound is tight by presenting an AfA verifier for NP-complete problem SUBSETSUM. We also show that AfAs can verify certain non-affine and non-stochastic unary languages.

yearjournalcountryeditionlanguage
2021-01-01
https://doi.org/10.1007/978-3-030-87993-8_6