The search functionality is under construction.

The search functionality is under construction.

A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (*f* : {0,1}^{n} *Z*). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.756-766

- Publication Date
- 1999/05/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

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.

Copy

Masaki NAKANISHI, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, "An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 5, pp. 756-766, May 1999, doi: .

Abstract: A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (*f* : {0,1}^{n} *Z*). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_756/_p

Copy

@ARTICLE{e82-a_5_756,

author={Masaki NAKANISHI, Kiyoharu HAMAGUCHI, Toshinobu KASHIWABARA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division},

year={1999},

volume={E82-A},

number={5},

pages={756-766},

abstract={A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (*f* : {0,1}^{n} *Z*). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 756

EP - 766

AU - Masaki NAKANISHI

AU - Kiyoharu HAMAGUCHI

AU - Toshinobu KASHIWABARA

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 1999

AB - A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (*f* : {0,1}^{n} *Z*). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.

ER -