Volume 19, No 1, 2012, P. 3340
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 stopoperator 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 stopoperators 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 stopoperator, synthesis, reliability.
Grabovskaia Svetlana Mikhailovna ^{1}
1. Penza State University,
40 Krasnaya str., 440026 Penza, Russia
email: swetazin@mail.ru
