Questions tagged [binary-decision-diagrams]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
43 views

Operations on Sentential Decision Diagrams

I've been recently reading about decision diagrams and their variants and came across sentential decision diagrams (paper here http://reasoning.cs.ucla.edu/fetch.php?id=121&type=pdf). The paper ...
user avatar
1 vote
0 answers
69 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 ...
user avatar
  • 223
5 votes
0 answers
246 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 ...
user avatar
4 votes
1 answer
160 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 ...
user avatar
  • 223
10 votes
1 answer
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 ...
user avatar
4 votes
1 answer
238 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-...
user avatar
3 votes
1 answer
450 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 $...
user avatar
  • 523
7 votes
0 answers
153 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 ...
user avatar
10 votes
0 answers
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 ...
user avatar
  • 1,338
7 votes
2 answers
345 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 ...
user avatar
  • 343
7 votes
2 answers
245 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 ...
user avatar
  • 343
15 votes
1 answer
786 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 ...
user avatar
  • 1,338
8 votes
4 answers
362 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 ...
user avatar