Volume 19, No 1, 2012, P. 33-40

UDC 519.718
S. M. Grabovskaya 
About the reliability of nonbranching programs in the basis of a generalized conjunction

Abstract:
The problem of synthesis of nonbranching programs with conditional stop-operator is considered in a full finite basis which contains functions of the form $x_1\cdot x_2$, $\overline x_1\cdot x_2$ or $\overline x_1\cdot\overline x_2$. All functional operators are supposed to be prone to output inverse failures with probability $\varepsilon\in(0,1/2)$ and conditional stop-operators are absolutely reliable. Any Boolean function is proved to be realized by a nonbranching program with unreliability no more then $\varepsilon+59\varepsilon^2$ at $\varepsilon\in(0,1/960]$.
Ill. 1, bibliogr. 4.

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

Grabovskaia Svetlana Mikhailovna ¹
1. Penza State University,
40 Krasnaya str., 440026 Penza, Russia
e-mail: swetazin@mail.ru