Talk About Network

Google


Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Electronic Equipment > LSI > BDD algorithm f...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 1 of 1 Topic 97 of 125
Post > Topic >>

BDD algorithm for image space of a finite function

by acd <acd4usenet@[EMAIL PROTECTED] > Jun 7, 2007 at 11:57 PM

I asked this already in comp.theory but did not get an answer

For a current project I needed a way to determine the
size of the image space of a finite function and came up with the
following algorithm:

I use BDDs  (more precisely Reduced Ordered Binary Decision Diagrams)
to represent the function f.
Hence, we have a vector F=(f_0,...,f_{k-1}) which represents the
function.
The enumeration is a recursive process:

enum_space(F) = enum_space_recursive(f,0,true);

enum_space_recursive(f,i,cond)
BEGIN

 if (i>= k) return 1
 else

res_true = 0; res_false=0;
 cond_true = cond AND f_i;
    if (cond_true <> FALSE)
       res_true = enum_space_recursive(f,i+1,cond_true);
    cond_false = cond AND  (NOT f_i);
    if (cond_false <> FALSE)
       res_true = enum_space_recursive(f,i+1,cond_false);

return res_true + res_false;
END;

Note that cond, cond_true, and cond_false are functions as well
and that the cmparisons with FALSE represent a satisfiability test.
For the cases I needed the method it works quite well and is
much faster than enumerating the image space
by brute force enumeration of the function domain and evaluation of
the function.
I have used the BDD-package CUDD.

Is this method known and published?
Maybe it has even a partuclar name?
I would like to give a reference even  if I came up with it
independently.

Thanks in advance,
Andreas
 




 1 Posts in Topic:
BDD algorithm for image space of a finite function
acd <acd4usenet@[EMAIL  2007-06-07 23:57:24 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Fri Oct 10 14:37:21 CDT 2008.