|
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.
Citation:
S. M. Grabovskaya, “An upper bound for reliability of non-branching programs with an unreliable stop-operator”, Prikl. Diskr. Mat. Suppl., 2015, no. 8, 106–108
Linking options:
https://www.mathnet.ru/eng/pdma214 https://www.mathnet.ru/eng/pdma/y2015/i8/p106
|
Statistics & downloads: |
Abstract page: | 97 | Full-text PDF : | 32 | References: | 27 |
|