The hazard-free (Kleene ternary, {0,u,1}) generalization of the Boolean decision-tree query model, in which queried bits and outputs may be unknown and the tree outputs a definite value only when the Boolean function is determined. Covers hazard-free decision-tree depth and size, the exponential separations from the Boolean model (the multiplexer is evasive; AND needs exponential size), constructions of hazard-free trees from Boolean trees (size at most 2s-1, optimal; a k-unknown parameterized bound), lower bounds via prime implicants and implicates and via 2*size(f)-1, and a hazard-free Sensitivity Theorem showing hazard-free sensitivity, block sensitivity, and certificate complexity are polynomially equivalent to hazard-free decision-tree depth.
This paper introduces hazard-free decision trees, a ternary (Kleene three-valued {0,u,1}) generalization of the classical Boolean decision-tree query model. In a hazard-free decision tree each querie…