Exact Affine OBDDs.
Rishat Ibrahimov, Kamil Ravilevich Khadiev, Abuzer Yakaryılmaz · arXiv (Cornell University) · 2017
We introduce affine OBDD model and we show that exact affine OBDDs can be exponentially narrower than bounded-error quantum and classical OBDDs on some certain problems. Moreover, we consider Las-Vegas quantum and classical automata models and improve the previous gap between deterministic and probabilistic models by a factor of 2 and then follow the same gap for the known most restricted quantum model. Lastly, we follow an exponential gap between exact affine finite automata and Las-Vegas classical and quantum models.