Error-Free Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Ravilevich Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz · International Journal of Foundations of Computer Science · 2021
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.