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

University proceedings. Volga region. Physical and mathematical sciences, 2009 Issue 2, Pages 60–67 (Mi ivpnz684)

Mathematics

Synthesis of asymptotically optimal non-branching programs in the basis of $\{x_1\vee x_2, x_1 \& x_2, \bar{x}_1, stop\}$

M. A. Alekhina, S. M. Zinovyeva

Penza State University, Penza

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).

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

UDC: 519.95



© Steklov Math. Inst. of RAS, 2024