Size and variable ordering of OBDDs representing threshold functions

DOI10.1007/BFB0045076MaRDI QIDQ4364580zbMATH OpenFDO

Authors Mitsushi Nouzoe, Y. Takenaga, S. Yajima

Publication date 4 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0045076

zbMATH Keywords

Boolean functiongraph representationlower boundordered binary decision diagramsthreshold functions

Mathematics Subject Classification ID

Boolean functions (06E30) Logic programming (68N17) Computer science aspects of computer-aided design (68U07)

Review text

The size of ordered binary decision diagrams (OBBDs) representing threshold functions is discussed. The lower bound on the OBBD size necessary to represent any threshold function when the variable ordering can be chosen adaptively to minimize the OBBD size is proved. It is shown, that it is not possible to find a good variable ordering only from the total order of weights, that is, for any variable ordering of this kind, there exists a threshold function that requires an exponential size OBBD, but is represented in polynomial size by the optimal ordering. For the entire collection see [Zbl 0869.00027].

Recommendations

• Size of ordered binary decision diagrams representing threshold functions
• On the size of ordered binary decision diagrams representing threshold functions
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• On the size of (generalized) OBDDs for threshold functions
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

Cited in

(10)

• On threshold BDDs and the optimal variable ordering problem
• Size of ordered binary decision diagrams representing threshold functions
• On the influence of the variable ordering for algorithmic learning using OBDDs
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• Restrictive Acceptance Suffices for Equivalence Problems
• On the size of ordered binary decision diagrams representing threshold functions
• Variable orderings and the size of OBDDs for random partially symmetric Boolean functions
• Size of OBDD representation of 2-level redundancies functions
• Output-size sensitiveness of OBDD construction through maximal independent set problem
• On the size of (generalized) OBDDs for threshold functions

This page was built for publication: Size and variable ordering of OBDDs representing threshold functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4364580)