Create Reduced Ordered Binary Decision Diagram (ROBDD) from truth table
Is there a software package (preferable an application, not library) that creates Reduced Ordered Binary Decision Diagrams (ROBDDs) from a given truth table (in some text format)?
logic solver truthtable binary-decision-diagram
add a comment |
Is there a software package (preferable an application, not library) that creates Reduced Ordered Binary Decision Diagrams (ROBDDs) from a given truth table (in some text format)?
logic solver truthtable binary-decision-diagram
add a comment |
Is there a software package (preferable an application, not library) that creates Reduced Ordered Binary Decision Diagrams (ROBDDs) from a given truth table (in some text format)?
logic solver truthtable binary-decision-diagram
Is there a software package (preferable an application, not library) that creates Reduced Ordered Binary Decision Diagrams (ROBDDs) from a given truth table (in some text format)?
logic solver truthtable binary-decision-diagram
logic solver truthtable binary-decision-diagram
asked Mar 25 '13 at 8:07
tomashtomash
370317
370317
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
add a comment |
With any BDD library you can do what you want. Of course, you must write a piece of code by yourself.
If you are looking for a lightweight tool, I often use an applet like this to have a quick look at the BDD of a function:
http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
add a comment |
BDDs are a memory constrained data structure because of the heavy reliance on detecting duplicate sub-truthtables. Most BDD packages you'll find aren't exactly a good fit for large, general truth tables, instead optimized for very sparse or highly repetitive expressions.
With the standard BDD packages, you work with expressions operating on variables. So you'd have to iterate over your truth table, constructing something like a product-of-sums expression for 1s in the table. Along the way, most libraries will dynamically reorder the variables to fit memory constraints, causing another huge slowdown. After around 24 variables, even with very sparse truth tables, these libraries will start to thrash on modern systems.
If you're only looking for the final BDD nodes given a truth table with its variable ordering already implicitly defined, you can skip a lot of the complexity with external libraries and horrible runtimes, just using some Unix text processing tools.
A good resource on BDDs, Knuth's TAOCP v4.1b, shows the equivalence of BDD nodes and their "beads," sub-truthtables that are non-square strings. I'm going to address a simpler version, ZDDs which have similar structures called "zeads": positive part sub-truthtables that are not completely zero. To generalize back to BDDs, replace sed+grep in the pipeline with a program filtering square strings instead of keeping positive part non-zero strings.
To print all the zeads of a truthtable (given as a one-line file of ascii '1's and '0's, newline at end), run the following command after setting the number of variables and filename:
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
This has many benefits over BDD packages:
- Simple with essentially no extraneous dependencies.
- External sorting means no thrashing unlike in-memory hash tables.
- Easily parallelizeable & scalable if you understand line buffering and disk caching when forking in the for loop.
- If writing to intermediate files sorting will parallelize too.
I use it regularly for truthtables up to 32 variables large, which are impossible to realistically come up with using BDD libraries. It doesn't tax the memory system at all, barely using a few MBs. But if you have a ton of RAM available, a decent OS like Linux will gladly use it all for caching disk to make it even faster.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f15610219%2fcreate-reduced-ordered-binary-decision-diagram-robdd-from-truth-table%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
add a comment |
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
add a comment |
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
answered Jun 10 '13 at 14:48
remustataremustata
6124
6124
add a comment |
add a comment |
With any BDD library you can do what you want. Of course, you must write a piece of code by yourself.
If you are looking for a lightweight tool, I often use an applet like this to have a quick look at the BDD of a function:
http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
add a comment |
With any BDD library you can do what you want. Of course, you must write a piece of code by yourself.
If you are looking for a lightweight tool, I often use an applet like this to have a quick look at the BDD of a function:
http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
add a comment |
With any BDD library you can do what you want. Of course, you must write a piece of code by yourself.
If you are looking for a lightweight tool, I often use an applet like this to have a quick look at the BDD of a function:
http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/
With any BDD library you can do what you want. Of course, you must write a piece of code by yourself.
If you are looking for a lightweight tool, I often use an applet like this to have a quick look at the BDD of a function:
http://tams-www.informatik.uni-hamburg.de/applets/java-bdd/
answered Mar 25 '13 at 13:27
LorenzoLorenzo
5641020
5641020
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
add a comment |
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
The provided page is not exactly what I wanted. I would like to provide a truth table and calculate ROBDD for it (that is, a Reduced OBDD), which is the smallest BDD-based representation of a given function. The page does not allow anything of that.
– tomash
Mar 27 '13 at 11:26
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
Well, it draw a ROBDD from a function given as an expression (not a truth table, indeed). The output is a ROBDD although the title says only BDD. Or you are looking for the best variables order?
– Lorenzo
Mar 27 '13 at 13:53
add a comment |
BDDs are a memory constrained data structure because of the heavy reliance on detecting duplicate sub-truthtables. Most BDD packages you'll find aren't exactly a good fit for large, general truth tables, instead optimized for very sparse or highly repetitive expressions.
With the standard BDD packages, you work with expressions operating on variables. So you'd have to iterate over your truth table, constructing something like a product-of-sums expression for 1s in the table. Along the way, most libraries will dynamically reorder the variables to fit memory constraints, causing another huge slowdown. After around 24 variables, even with very sparse truth tables, these libraries will start to thrash on modern systems.
If you're only looking for the final BDD nodes given a truth table with its variable ordering already implicitly defined, you can skip a lot of the complexity with external libraries and horrible runtimes, just using some Unix text processing tools.
A good resource on BDDs, Knuth's TAOCP v4.1b, shows the equivalence of BDD nodes and their "beads," sub-truthtables that are non-square strings. I'm going to address a simpler version, ZDDs which have similar structures called "zeads": positive part sub-truthtables that are not completely zero. To generalize back to BDDs, replace sed+grep in the pipeline with a program filtering square strings instead of keeping positive part non-zero strings.
To print all the zeads of a truthtable (given as a one-line file of ascii '1's and '0's, newline at end), run the following command after setting the number of variables and filename:
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
This has many benefits over BDD packages:
- Simple with essentially no extraneous dependencies.
- External sorting means no thrashing unlike in-memory hash tables.
- Easily parallelizeable & scalable if you understand line buffering and disk caching when forking in the for loop.
- If writing to intermediate files sorting will parallelize too.
I use it regularly for truthtables up to 32 variables large, which are impossible to realistically come up with using BDD libraries. It doesn't tax the memory system at all, barely using a few MBs. But if you have a ton of RAM available, a decent OS like Linux will gladly use it all for caching disk to make it even faster.
add a comment |
BDDs are a memory constrained data structure because of the heavy reliance on detecting duplicate sub-truthtables. Most BDD packages you'll find aren't exactly a good fit for large, general truth tables, instead optimized for very sparse or highly repetitive expressions.
With the standard BDD packages, you work with expressions operating on variables. So you'd have to iterate over your truth table, constructing something like a product-of-sums expression for 1s in the table. Along the way, most libraries will dynamically reorder the variables to fit memory constraints, causing another huge slowdown. After around 24 variables, even with very sparse truth tables, these libraries will start to thrash on modern systems.
If you're only looking for the final BDD nodes given a truth table with its variable ordering already implicitly defined, you can skip a lot of the complexity with external libraries and horrible runtimes, just using some Unix text processing tools.
A good resource on BDDs, Knuth's TAOCP v4.1b, shows the equivalence of BDD nodes and their "beads," sub-truthtables that are non-square strings. I'm going to address a simpler version, ZDDs which have similar structures called "zeads": positive part sub-truthtables that are not completely zero. To generalize back to BDDs, replace sed+grep in the pipeline with a program filtering square strings instead of keeping positive part non-zero strings.
To print all the zeads of a truthtable (given as a one-line file of ascii '1's and '0's, newline at end), run the following command after setting the number of variables and filename:
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
This has many benefits over BDD packages:
- Simple with essentially no extraneous dependencies.
- External sorting means no thrashing unlike in-memory hash tables.
- Easily parallelizeable & scalable if you understand line buffering and disk caching when forking in the for loop.
- If writing to intermediate files sorting will parallelize too.
I use it regularly for truthtables up to 32 variables large, which are impossible to realistically come up with using BDD libraries. It doesn't tax the memory system at all, barely using a few MBs. But if you have a ton of RAM available, a decent OS like Linux will gladly use it all for caching disk to make it even faster.
add a comment |
BDDs are a memory constrained data structure because of the heavy reliance on detecting duplicate sub-truthtables. Most BDD packages you'll find aren't exactly a good fit for large, general truth tables, instead optimized for very sparse or highly repetitive expressions.
With the standard BDD packages, you work with expressions operating on variables. So you'd have to iterate over your truth table, constructing something like a product-of-sums expression for 1s in the table. Along the way, most libraries will dynamically reorder the variables to fit memory constraints, causing another huge slowdown. After around 24 variables, even with very sparse truth tables, these libraries will start to thrash on modern systems.
If you're only looking for the final BDD nodes given a truth table with its variable ordering already implicitly defined, you can skip a lot of the complexity with external libraries and horrible runtimes, just using some Unix text processing tools.
A good resource on BDDs, Knuth's TAOCP v4.1b, shows the equivalence of BDD nodes and their "beads," sub-truthtables that are non-square strings. I'm going to address a simpler version, ZDDs which have similar structures called "zeads": positive part sub-truthtables that are not completely zero. To generalize back to BDDs, replace sed+grep in the pipeline with a program filtering square strings instead of keeping positive part non-zero strings.
To print all the zeads of a truthtable (given as a one-line file of ascii '1's and '0's, newline at end), run the following command after setting the number of variables and filename:
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
This has many benefits over BDD packages:
- Simple with essentially no extraneous dependencies.
- External sorting means no thrashing unlike in-memory hash tables.
- Easily parallelizeable & scalable if you understand line buffering and disk caching when forking in the for loop.
- If writing to intermediate files sorting will parallelize too.
I use it regularly for truthtables up to 32 variables large, which are impossible to realistically come up with using BDD libraries. It doesn't tax the memory system at all, barely using a few MBs. But if you have a ton of RAM available, a decent OS like Linux will gladly use it all for caching disk to make it even faster.
BDDs are a memory constrained data structure because of the heavy reliance on detecting duplicate sub-truthtables. Most BDD packages you'll find aren't exactly a good fit for large, general truth tables, instead optimized for very sparse or highly repetitive expressions.
With the standard BDD packages, you work with expressions operating on variables. So you'd have to iterate over your truth table, constructing something like a product-of-sums expression for 1s in the table. Along the way, most libraries will dynamically reorder the variables to fit memory constraints, causing another huge slowdown. After around 24 variables, even with very sparse truth tables, these libraries will start to thrash on modern systems.
If you're only looking for the final BDD nodes given a truth table with its variable ordering already implicitly defined, you can skip a lot of the complexity with external libraries and horrible runtimes, just using some Unix text processing tools.
A good resource on BDDs, Knuth's TAOCP v4.1b, shows the equivalence of BDD nodes and their "beads," sub-truthtables that are non-square strings. I'm going to address a simpler version, ZDDs which have similar structures called "zeads": positive part sub-truthtables that are not completely zero. To generalize back to BDDs, replace sed+grep in the pipeline with a program filtering square strings instead of keeping positive part non-zero strings.
To print all the zeads of a truthtable (given as a one-line file of ascii '1's and '0's, newline at end), run the following command after setting the number of variables and filename:
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
This has many benefits over BDD packages:
- Simple with essentially no extraneous dependencies.
- External sorting means no thrashing unlike in-memory hash tables.
- Easily parallelizeable & scalable if you understand line buffering and disk caching when forking in the for loop.
- If writing to intermediate files sorting will parallelize too.
I use it regularly for truthtables up to 32 variables large, which are impossible to realistically come up with using BDD libraries. It doesn't tax the memory system at all, barely using a few MBs. But if you have a ton of RAM available, a decent OS like Linux will gladly use it all for caching disk to make it even faster.
edited Nov 28 '18 at 3:29
Samuel Liew♦
45.3k32116155
45.3k32116155
answered Feb 11 '15 at 13:42
user2875414
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f15610219%2fcreate-reduced-ordered-binary-decision-diagram-robdd-from-truth-table%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown