Questions tagged [binary-decision-diagrams]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
67 views

Combinatorial problems in electronics

This could be a downvoted question but I am asking because I am not able to get usable info via Google. Are there any interesting combinatorial problems in the field of electronics circuits design? I ...
10
votes
1answer
273 views

Algorithms on graphs represented using BDDs

The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong ...
5
votes
0answers
244 views

Less known graphical representations of Boolean functions

A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other ...
4
votes
1answer
158 views

Compatible partial permutations

Please, correct my terminology as I am not a combinatorician (I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem. Let $P_k$ be ...
15
votes
1answer
770 views

Most significant bit of integer multiplication and binary decision diagrams

Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\ $ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the ...
4
votes
1answer
234 views

Trade off between width and depth of free BDDs for total functions

Terminology A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has out-...
3
votes
1answer
419 views

Bounds on the size of smallest decision tree for a boolean function?

Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$? It seems to me that assuming $...
7
votes
2answers
336 views

Boolean functions with exponential size OBDD representation in all orders except one order?

Are there boolean functions with exponential size OBDD representation in all orders except one order? ...exponential size in all orders except very few orders? The exceptional orders should be ...
7
votes
0answers
151 views

Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?

In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
10
votes
0answers
283 views

Lower bound method for ordered binary decision diagrams

This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?: If you want to prove some exponential ...
7
votes
2answers
244 views

Boolean function with specific ОBDD representation

I am looking for a class of boolean functions on $n$ variables with the following property: When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD ...
8
votes
4answers
360 views

Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how ...