|
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.
Citation:
S. M. Grabovskaya, “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}$”, University proceedings. Volga region. Physical and mathematical sciences, 2010, no. 4, 26–38
Linking options:
https://www.mathnet.ru/eng/ivpnz652 https://www.mathnet.ru/eng/ivpnz/y2010/i4/p26
|
Statistics & downloads: |
Abstract page: | 19 | Full-text PDF : | 2 | References: | 7 |
|