On the arbitrarily reliable implementation of~Boolean~functions by non-branching programs with~a conditional stop operator in~bases~with~generalized conjunction

S. M. Grabovskaya ; M. A. Alekhina

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 70-77

Résumé

The implementation of Boolean functions by non-branching programs with a conditional stop operator is considered in a complete finite basis containing a generalized conjunction, i.e. a function of the form $x_1^{\alpha_1}\ x_2^{\alpha_2}$ $(\alpha_1, \alpha_2 \in \{0, 1\})$. The computational operators are assumed to go into faulty states of an arbitrary type independently of each other with a probability not exceeding the value $N(B)$, i.e. unreliability of the most unreliable (“bad”) of the basic elements. In addition, conditional stop operators are also unreliable and independently of each other are prone to two types of faults: the first and second kind. The fault of the first kind is characterized by the fact that on admission to the stop-operator input unit this operator does not work with a probability $\delta \in (0, 1/2)$ and, therefore, the program work continues. The fault of the second kind is that on admission to the stop-operator input zero this operator works with probability $\eta \in (0, 1/2)$, and, hence, the program work stops. Denote $\mu=\max\{\delta, \eta\}$. To increase the reliability of source programs, we use the function $g(x_1, x_2, x_3, x_4)$ of the form $(x_1^{\sigma_1}x_2^{\sigma_2}\vee x_3^{\sigma_3}x_4^{\sigma_4})^{\sigma_5}$ $(\sigma_i \in \{0, 1\}, i \in \{1, 2, 3, 4, 5\})$ and the method of multiple duplication of circuits and programs. We prove that if the complete finite basis $B$ contains a function of the form $x_1^{\alpha_1}\ x_2^{\alpha_2}$ $(\alpha_1, \alpha_2 \in \{0, 1\})$, then any Boolean function $f$ can be implemented by a non-branching program with unreliability no more than $[0{,}84]^t\cdot 5{,}17\cdot N(B)$ for any natural $t$ with $N(B)\in (0, 1/960]$ and $\mu \in (0, 1/10]$. So, it is proved that an arbitrary Boolean function can be implemented with an arbitrarily reliable non-branching program.

Détail

Keywords: Boolean function, non-branching program, conditional stop operator, synthesis, reliability.