@inproceedings{f363f30eced04df0ac0cd476541b2ba6,
title = "Affine Automata Verifiers",
abstract = "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.",
keywords = "Affine automata, Arthur-Merlin games, Interactive proof systems, NP, Subset-sum problem, Unary languages",
author = "Aliya Khadieva and Abuzer Yakaryilmaz",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",
year = "2021",
doi = "10.1007/978-3-030-87993-8\_6",
language = "English",
isbn = "9783030879921",
volume = "12984 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "84--100",
editor = "Irina Kostitsyna and Pekka Orponen",
booktitle = "Unconventional Computation and Natural Computation - 19th International Conference, UCNC 2021, Proceedings",
address = "Germany",
}