@inproceedings{1d7acb4a0ba341568ad928c3e3fd4615,
title = "Error-free affine, unitary, and probabilistic OBDDS",
abstract = "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.",
keywords = "Affine models, Las Vegas computation, OBDDs, Quantum and probabilistic computation, Succinctness, Zero-error",
author = "Rishat Ibrahimov and Kamil Khadiev and Kri{\v s}jānis Prūsis and Abuzer Yakaryılmaz",
note = "Publisher Copyright: {\textcopyright} IFIP International Federation for Information Processing 2018.; 20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2018 ; Conference date: 25-07-2018 Through 27-07-2018",
year = "2018",
doi = "10.1007/978-3-319-94631-3\_15",
language = "English",
isbn = "9783319946306",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "175--187",
editor = "Stavros Konstantinidis and Giovanni Pighizzini",
booktitle = "Descriptional Complexity of Formal Systems - 20th IFIP WG 1.02 International Conference, DCFS 2018, Proceedings",
address = "Germany",
}