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.

Minato has proposed canonical representation for polynomial functions using zero-suppressed binary decision diagrams (ZBDDs). In this paper, we extend binary moment diagrams (BMDs) proposed by Bryant and Chen to handle variables with degrees higher than l. The experimental results show that this approach is much more efficient than the previous ZBDDs' approach. The proposed approach is expected to be useful for various problems, in particular, for computer algebra.