6533b7d8fe1ef96bd1269bbf

RESEARCH PRODUCT

Zero-Error Affine, Unitary, and Probabilistic OBDDs

Rishat IbrahimovKamil KhadievKrisjanis PrusisJevgenijs VihrovsAbuzer Yakaryilmaz

subject

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFormal Languages and Automata Theory (cs.FL)Computer Science::Logic in Computer ScienceFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Computer Science::Computational ComplexityComputer Science::Artificial IntelligenceQuantum Physics (quant-ph)Computer Science::Databases

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 by considering the automata versions of these models.

yearjournalcountryeditionlanguage
2017-03-21
http://arxiv.org/abs/1703.07184