|
Guest
|
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 |
|
|
