94 citations · 376 across the 55 of their papers we have counts for
10 papers · 1 filter
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…
Magic coins are useful for small-space quantum machines
A. C. Cem Say, Abuzer Yakaryilmaz
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to…
Alternating, private alternating, and quantum alternating realtime automata
Gökalp Demirci, Mika Hirvensalo, Klaus Reinhardt +2
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-count…
Quantum finite automata: A modern introduction
A. C. Cem Say, Abuzer Yakaryilmaz
We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum comp…
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…
Classical automata on promise problems
Viliam Geffert, Abuzer Yakaryilmaz
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a f…