Error-free affine, unitary, and probabilistic OBDDs

Rishat Ibrahimov; Kamil Khadiev; Krišjānis Prūsis; Abuzer Yakaryilmaz

doi:10.1142/S0129054121500246

Error-free affine, unitary, and probabilistic OBDDs

Rishat Ibrahimov^*
, Kamil Khadiev
, Krišjānis Prūsis
, Abuzer Yakaryilmaz

^*Šī darba korespondējošais autors

Datorikas nodaļa

Smart Quantum Technologies Ltd.
Yandex
Kazan Volga Region Federal University

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

9 Atsauces (Scopus)

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Lapas (no-līdz)	827-847
Lapu skaits	21
Žurnāls	International Journal of Foundations of Computer Science
Sējums	32
Izdevuma numurs	7
DOIs	https://doi.org/10.1142/S0129054121500246
Publikācijas statuss	Publicēts - 1 nov. 2021

OECD Zinātnes nozare

1.2 Datorzinātne un informātika

Piekļuve Dokumentiem

10.1142/S0129054121500246

Citi faili un saites

Citēt šo

@article{5099b99a339443978bba6a20be5e8802,

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 counterparts of these models.",

keywords = "Affine automata, Las-Vegas algorithms, OBDDs, Quantum and probabilistic computation, State complexity, Zero-error",

author = "Rishat Ibrahimov and Kamil Khadiev and Kri{\v s}jānis Prūsis and Abuzer Yakaryilmaz",

note = "Publisher Copyright: {\textcopyright} 2021 World Scientific Publishing Company.",

year = "2021",

month = nov,

day = "1",

doi = "10.1142/S0129054121500246",

language = "English",

volume = "32",

pages = "827--847",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "7",

}

TY - JOUR

T1 - Error-free affine, unitary, and probabilistic OBDDs

AU - Ibrahimov, Rishat

AU - Khadiev, Kamil

AU - Prūsis, Krišjānis

AU - Yakaryilmaz, Abuzer

PY - 2021/11/1

Y1 - 2021/11/1

N2 - 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.

AB - 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.

KW - Affine automata

KW - Las-Vegas algorithms

KW - OBDDs

KW - Quantum and probabilistic computation

KW - State complexity

KW - Zero-error

UR - https://www.worldscientific.com/doi/abs/10.1142/S0129054121500246

UR - https://www.scopus.com/pages/publications/85106157600

U2 - 10.1142/S0129054121500246

DO - 10.1142/S0129054121500246

M3 - Article

SN - 0129-0541

VL - 32

SP - 827

EP - 847

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 7

ER -