Abstract:
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 $\varepsilon\in(0,1/2)$. Conditional stop-operators are subject to faults of two types: the first and the second kinds with probabilities $\delta\in(0,1/2)$ and $\eta\in(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\{\varepsilon,\eta\}+78\mu^2$ for each $\varepsilon\in(0,1/960]$ and $\mu=\max\{\varepsilon,\delta,\eta\}$.
Keywords:Boolean function, non-branching program, conditional stop operator, reliability, constant faults on the outputs.