Computer Science – Computational Complexity
Scientific paper
2010-08-10
EPTCS 31, 2010, pp. 27-37
Computer Science
Computational Complexity
In Proceedings DCFS 2010, arXiv:1008.1270
Scientific paper
10.4204/EPTCS.31.5
Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR} and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We introduce and study a class of functions with the following property: Instead of evaluating an extension of a boolean function on a given set of transients, it is possible to get the same value by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.
Brzozowski Janusz
Li Baiyu
Ye Yuli
No associations
LandOfFree
On the Complexity of the Evaluation of Transient Extensions of Boolean Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of the Evaluation of Transient Extensions of Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of the Evaluation of Transient Extensions of Boolean Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583308