94 citations · 376 across the 55 of their papers we have counts for
25 papers · 1 filter
Two-way affine automata can verify every language
Zeyu Chen, Abuzer Yakaryılmaz
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…
Real-valued affine automata compute beyond Turing machines
Abuzer Yakaryılmaz
We show that bounded-error affine finite automata recognize uncountably many (and so some non-Turing recognizable) languages when using real-valued transitions.
Classical and quantum Merlin-Arthur automata
Abuzer Yakaryılmaz
We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate at the beginning of computation and it is scanned by Arthur before reading the input. We define Merlin-…
Improved constructions for succinct affine automata
Abuzer Yakaryılmaz
Affine finite automata (AfA) can be more succinct than probabilistic and quantum finite automata when recognizing some regular languages with bounded-error. In this paper, we impro…
Affine automata verifiers
Aliya Khadieva, Abuzer Yakaryılmaz
We initiate the study of the verification power of AfAs as part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Th…
New Results on Vector and Homing Vector Automata
Özlem Salehi, Abuzer Yakaryılmaz, A. C. Cem Say
We present several new results and connections between various extensions of finite automata through the study of vector automata and homing vector automata. We show that homing ve…