An upper bound for reliability of non-branching programs with an unreliable stop-operator

A realization of Boolean functions by non-branching programs with a conditional stop-operator is considered in an arbitrary complete finite basis. All computational operators are supposed to be subject to output one-type constant faults with a probability e e (0,1/2). Conditional stop-operators are subject to faults of two types: the first and the second kinds with probabilities 8 e (0,1/2) and n e (0,1/2) respectively. Three bases are considered: with a special function, with the generalized disjunction, and with the generalized conjunction. Some upper bounds for the reliability of non-branching programs in these bases are given. For an arbitrary complete finite basis, such a bound is equal to max{e, n} + 78ц for each e e (0,1/960] and ц = max{e, 8, n}.

Keywords

Authors

References