6533b7d1fe1ef96bd125d51e

RESEARCH PRODUCT

Error-Free Affine, Unitary, and Probabilistic OBDDs

Rishat IbrahimovKrišjānis PrūsisAbuzer YakaryilmazKamil Khadiev

subject

Discrete mathematicsState complexityComputer Science::Logic in Computer ScienceComputer Science (miscellaneous)Probabilistic logicAffine transformationComputer Science::Computational ComplexityComputer Science::Artificial IntelligenceUnitary stateComputer Science::DatabasesMathematicsZero error

description

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.

yearjournalcountryeditionlanguage
2021-05-12International Journal of Foundations of Computer Science
https://doi.org/10.1142/s0129054121500246