3 citations · 4 across the 5 of their papers we have counts for
5 papers
Nondeterministic unitary OBDDs
Aida Gainutdinova, Abuzer Yakaryılmaz
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling set…
Unary probabilistic and quantum automata on promise problems
Aida Gainutdinova, Abuzer Yakaryilmaz
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error…
New results on classical and quantum counter automata
Masaki Nakanishi, Abuzer Yakaryılmaz, Aida Gainutdinova
We show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation res…
Very narrow quantum OBDDs and width hierarchies for classical OBDDs
Farid Ablayev, Aida Gainutdinova, Kamil Khadiev +1
We present several results on comparative complexity for different variants of OBDD models. - We present some results on comparative complexity of classical and quantum OBDDs. We c…
On Computational Power of Quantum Branching Programs
Farid Ablayev, Aida Gainutdinova, Marek Karpinski
In this paper we study a model of a Quantum Branching Program (QBP) and investigate its computational power. We prove a general lower bound on the width of read-once QBPs, which we…