94 citations · 376 across the 55 of their papers we have counts for
3 papers · 1 filter
Postselecting probabilistic finite state recognizers and verifiers
Maksims Dimitrijevs, Abuzer Yakaryılmaz
In this paper, we investigate the computational and verification power of bounded-error postselecting realtime probabilistic finite state automata (PostPFAs). We show that PostPFAs…
Probabilistic verification of all languages
Maksims Dimitrijevs, Abuzer Yakaryılmaz
We present three protocols for verifying all languages: (i) For any unary (binary) language, there is a log-space (linear-space) interactive proof system (IPS); (ii) for any langua…
New Size Hierarchies for Two Way Automata
Kamil Khadiev, Rishat Ibrahimov, Abuzer Yakary
We introduce a new type of nonuniform two--way automaton that can use a different transition function for each tape square. We also enhance this model by allowing to shuffle the gi…