Abstract:
The composition tree of a given function, when it exists,
provides a representation of the function revealing all possible
disjunctive decompositions, thereby suggesting a realization
of the function at a minimal cost.
Previously and independently, the authors had studied the
class of multiple-valued functions that are fully sensitive to
their variables.
These functions are useful for test generation purposes,
and almost all m-valued n-variable
functions belong to this class as n increases.
All functions in this class have composition trees.
This paper presents a recursive algorithm for generating the
composition tree for any function in this class.
The construction proceeds top-down and makes immediate use
of any encountered decomposition, which reduces
the (in general exponential) computation time.
In:
Proceedings of the 27th IEEE International Symposium on
Multiple Valued Logic (1997), 19-26.
gz-compressed POSTSCRIPT-file (47 kB, 8 pages)
Back
to Bernhard von Stengel's list of publications