RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2015 Issue 8, Pages 106–108 (Mi pdma214)

Mathematical Foundations of Reliability of Computing and Control Systems

An upper bound for reliability of non-branching programs with an unreliable stop-operator

S. M. Grabovskaya

Penza State University, Penza

Abstract: A realization of Boolean functions by non-branching programs with a conditional stop-operator is considered in an arbitrary complete finite basis. All computational operators are supposed to be subject to output one-type constant faults with a probability $\varepsilon\in(0,1/2)$. Conditional stop-operators are subject to faults of two types: the first and the second kinds with probabilities $\delta\in(0,1/2)$ and $\eta\in(0,1/2)$ respectively. Three bases are considered: with a special function, with the generalized disjunction, and with the generalized conjunction. Some upper bounds for the reliability of non-branching programs in these bases are given. For an arbitrary complete finite basis, such a bound is equal to $\max\{\varepsilon,\eta\}+78\mu^2$ for each $\varepsilon\in(0,1/960]$ and $\mu=\max\{\varepsilon,\delta,\eta\}$.

Keywords: Boolean function, non-branching program, conditional stop operator, reliability, constant faults on the outputs.

UDC: 519.71

DOI: 10.17223/2226308X/8/40



© Steklov Math. Inst. of RAS, 2024