RUS  ENG
Full version
JOURNALS // University proceedings. Volga region. Physical and mathematical sciences // Archive

University proceedings. Volga region. Physical and mathematical sciences, 2010 Issue 4, Pages 26–38 (Mi ivpnz652)

Mathematics

On the reliability of non-branching programs in a basis containing a function of the form $x_1^{\alpha_1} \vee x_2^{\alpha_2}$

S. M. Grabovskaya

Penza State University, Penza

Abstract: The problem of synthesis of nobranching programs with conditional stop-operator is considered in full finite basis, contained some kind function $x_1^{\alpha_1} \vee x_2^{\alpha_2}$, $\alpha_1, \alpha_2 \in \{0,1\}$. All functional operators are supposed to be prone output inverse failures with probability $\epsilon$ ($\epsilon \in (0,1/2)$). Conditional stop-operators are absolutely reliable. Any boolean function is proved to be possible to realize by nobranching program, functioned with unreliability no more $\epsilon+81\epsilon^2$ at $\epsilon \in (0,1/960]$.

Keywords: boolean functions, nobraching programs, conditional stop-operator, synthesis, reliability.

UDC: 519.718



© Steklov Math. Inst. of RAS, 2024