Abstract:
We consider the problem of synthesis of optimal on reliability nobranching programs with conditional stop-operator at inverse faults on operator outputs in basis $\{x_1\vee x_2, x_1 \& x_2, \bar{x}_1, stop\}$. We proved that in this basis it's possible to realize all Boolean functions with asymptotically optimal on reliability programs with conditional stop-operator, and for functions $x_i$ ($i \in \{1, 2, ..., n\}$) these programs are absolutely reliable (contain no operators), and for remaining functions these programs work with unreliability asymptotically equal $\epsilon$ at $\epsilon \to 0$ ($\epsilon$ is a probability of the inverse fault on the operator output).