6533b7d2fe1ef96bd125e9cf

RESEARCH PRODUCT

Error-Free Affine, Unitary, and Probabilistic OBDDs

Rishat IbrahimovKamil KhadievKamil KhadievAbuzer YakaryilmazKrišjānis Prūsis

subject

Discrete mathematicsQuadratic growthLas vegas010102 general mathematicsProbabilistic logic02 engineering and technologyComputer Science::Computational ComplexityComputer Science::Artificial Intelligence01 natural sciencesUnitary stateAutomatonSuccinctnessComputer Science::Logic in Computer Science0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingAffine transformation0101 mathematicsComputer Science::DatabasesZero errorMathematics

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 versions of these models.

yearjournalcountryeditionlanguage
2018-01-01
https://doi.org/10.1007/978-3-319-94631-3_15