Journal
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Volume 32, Issue 7, Pages 827-847Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0129054121500246
Keywords
OBDDs; affine automata; quantum and probabilistic computation; zero-error; Las-Vegas algorithms; state complexity
Categories
Funding
- Latvian State Research Programme NeXIT project [1]
- ERDF project [1.1.1.5/19/A/005]
- Kazan Federal University [0671-2020-0065]
- ERC Advanced Grant MQC
Ask authors/readers for more resources
The introduction of the affine OBDD model shows that zero-error affine OBDDs can be exponentially narrower on certain problems compared to bounded-error unitary and probabilistic OBDDs. Additionally, Las-Vegas unitary and probabilistic OBDDs are shown to be quadratically narrower than deterministic OBDDs. These results also hold true for the automata counterparts of these models.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
