Paper Info
Title
Nondeterministic Unitary Obdds
Abstract
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically "cheap" functions that are "expensive" for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
Year
DOI
Venue
2017
10.1007/978-3-319-58747-9_13
COMPUTER SCIENCE - THEORY AND APPLICATIONS (CSR 2017)
DocType
Volume
ISSN
Conference
10304
0302-9743
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Aida Gainutdinova1594.95
Abuzer Yakaryilmaz216825.31