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

^*Corresponding author for this work

Department of Computer Science

Smart Quantum Technologies Ltd.
Yandex
Kazan Volga Region Federal University

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

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.

Original language	English
Pages (from-to)	827-847
Number of pages	21
Journal	International Journal of Foundations of Computer Science
Volume	32
Issue number	7
DOIs	https://doi.org/10.1142/S0129054121500246
Publication status	Published - 1 Nov 2021

Keywords

Affine automata
Las-Vegas algorithms
OBDDs
Quantum and probabilistic computation
State complexity
Zero-error

OECD Field of Science

1.2 Computer and Information Sciences

Access to Document

10.1142/S0129054121500246

Cite this

@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 -

Error-free affine, unitary, and probabilistic OBDDs

Abstract

Keywords

OECD Field of Science

Access to Document

Other files and links

Cite this