Error-Free Affine, Unitary, and Probabilistic OBDDs - Descriptional Complexity of Formal Systems Access content directly
Conference Papers Year : 2018

Error-Free Affine, Unitary, and Probabilistic OBDDs

Rishat Ibrahimov
  • Function : Author
  • PersonId : 1038042
Kamil Khadiev
  • Function : Author
  • PersonId : 1038043
Krišjānis Prūsis
  • Function : Author
  • PersonId : 1038044
Abuzer Yakaryilmaz
  • Function : Author
  • PersonId : 1024587

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.
Fichier principal
Vignette du fichier
470153_1_En_15_Chapter.pdf (346.98 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01905639 , version 1 (26-10-2018)

Licence

Attribution

Identifiers

Cite

Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryilmaz. 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⟩
42 View
92 Download

Altmetric

Share

Gmail Facebook X LinkedIn More