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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905639
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:42 AM
Last modification on : Friday, November 9, 2018 - 7:58:02 AM
Long-term archiving on : Sunday, January 27, 2019 - 1:15:12 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryılmaz. Error-Free Affine, Unitary, and Probabilistic OBDDs. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.175-187, ⟨10.1007/978-3-319-94631-3_15⟩. ⟨hal-01905639⟩

Share

Metrics

Record views

61