IEICE TRANSACTIONS on Information
Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
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
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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
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
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
ER -
English
