On reliability of non-branching programs in a basis containing the generalized conjunction at arbitrary faults of computational operators

Background. The concept of non-branching programs is closely related to the concept of circuits of functional elements (FE). FE circuits are models of electronic circuits, and non-branching programs (both with conditional stop and without it) model the operation of computing devices. Despite these differences, reliability and complexity results obtained for FE circuits are transferred to non-branching programs without stop-operators and vice versa. Prior to the author's work, the problem of constructing reliable (and asymptotically optimal regarding reliability) non-branching programs with a conditional stop-operator has not been considered. For the first time this problem was researched for inverse faults at the outputs of computational operators, and then for the one-type constant faults at the outputs of computational operators. The question of reliability of non-branching programs for faults of arbitrary type still remains open. In this work the implementation of Boolean functions by non-branching programs with a conditional stop-operator is considered in a complete finite basis containing the generalized conjunction. It is assumed that the computational operators are prone to faults of arbitrary type independently of each other, and conditional stop-operators are absolutely reliable. Materials and methods. To raise the reliability of the aource circuits (programs), the iterative approach is used, i.e. multiple duplication of the source circuits (programs). In addition, a new method for constructing non-branching programs has been developed. Results. The work resulted in discovering an upper bound for the unreliability of non-branching programs with a conditional stop-operator in complete finite basis B , containing the generalized conjunction. Conclusions. If a complete finite basis contains the generalized conjunction, then any Boolean function can be implemented by a non-branching program with a conditional stop-operator of arbitrarily high preassigned reliability.