94 citations · 376 across the 55 of their papers we have counts for
7 papers · 1 filter
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…
On the computational power of affine automata
Mika Hirvensalo, Etienne Moutot, Abuzer Yakaryılmaz
We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language…
Decision problems on unary probabilistic and quantum automata
Mika Hirvensalo, Abuzer Yakaryılmaz
It is well known that the emptiness problem for binary probabilistic automata and so for quantum automata is undecidable. We present the current status of the emptiness problems fo…
Uncountable classical and quantum complexity classes
Maksims Dimitrijevs, Abuzer Yakaryılmaz
Polynomial--time constant--space quantum Turing machines (QTMs) and logarithmic--space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error…
Affine computation and affine automaton
Alejandro Díaz-Caro, Abuzer Yakaryılmaz
We introduce a quantum-like classical computational model, called affine computation, as a generalization of probabilistic computation. After giving the basics of affine computatio…
Can one quantum bit separate any pair of words with zero-error?
Aleksandrs Belovs, Juan Andres Montoya, Abuzer Yakaryılmaz
Determining the minimum number of states required by a finite automaton to separate a given pair of different words is an important problem. In this paper, we consider this problem…