An Upper Bound of Unreliability of Non-Branching Programs in an Arbitrary Complete Finite Basis for One-Type Constant Faults at the Outputs of Computational Operators

Abstract

The implementation of Boolean functions by non-branching programs with a conditional stop operator is considered in an arbitrary complete finite basis. We assume that conditional stop operators of the program are absolutely reliable while all computational operators are prone to the output one-type constant faults of either type 0 or type 1. An upper bound for unreliability of the programs was found in different bases. It was proved that in some cases any Boolean function can be implemented by the non-branching program of arbitrarily high preassigned reliability.