Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division

Takashi HORIYAMA; Shuzo YAJIMA

Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division

Takashi HORIYAMA, Shuzo YAJIMA

Full Text Views

0

Cite this

Summary :

An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2^(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.

Publication: IEICE TRANSACTIONS on Information Vol.E81-D No.8 pp.793-800

Publication Date: 1998/08/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Algorithm and Computational Complexity

Cite this

Copy

Takashi HORIYAMA, Shuzo YAJIMA, "Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division" in IEICE TRANSACTIONS on Information, vol. E81-D, no. 8, pp. 793-800, August 1998, doi: .
Abstract: An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2^(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_8_793/_p

Copy

@ARTICLE{e81-d_8_793,
author={Takashi HORIYAMA, Shuzo YAJIMA, },
journal={IEICE TRANSACTIONS on Information},
title={Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division},
year={1998},
volume={E81-D},
number={8},
pages={793-800},
abstract={An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2^(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
T2 - IEICE TRANSACTIONS on Information
SP - 793
EP - 800
AU - Takashi HORIYAMA
AU - Shuzo YAJIMA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 1998
AB - An Ordered Binary Decision Diagram (OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω ( 2^(n-i)/8 ) for any variable ordering. We also show that -OBDDs, -OBDDs and -OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of -OBDDs, -OBDDs and -OBDDs.
ER -