Geodesic
An upper bound for reliability of non-branching programs with an unreliable stop-operator
Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 106-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{PDMA_2015_8_a39,
     author = {S. M. Grabovskaya},
     title = {An upper bound for reliability of non-branching programs with an unreliable stop-operator},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {106--108},
     year = {2015},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2015_8_a39/}
}
TY  - JOUR
AU  - S. M. Grabovskaya
TI  - An upper bound for reliability of non-branching programs with an unreliable stop-operator
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2015
SP  - 106
EP  - 108
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/PDMA_2015_8_a39/
LA  - ru
ID  - PDMA_2015_8_a39
ER  - 
%0 Journal Article
%A S. M. Grabovskaya
%T An upper bound for reliability of non-branching programs with an unreliable stop-operator
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2015
%P 106-108
%N 8
%U http://geodesic.mathdoc.fr/item/PDMA_2015_8_a39/
%G ru
%F PDMA_2015_8_a39
S. M. Grabovskaya. An upper bound for reliability of non-branching programs with an unreliable stop-operator. Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 106-108. http://geodesic.mathdoc.fr/item/PDMA_2015_8_a39/

[1] Chashkin A. V., “O srednem vremeni vychisleniya znachenii bulevykh funktsii”, Diskretnyi analiz i issledovanie operatsii, 4:1 (1997), 60–78 | MR | Zbl

[2] Alekhina M. A., Sintez asimptoticheski optimalnykh po nadezhnosti skhem iz nenadezhnykh elementov, IITs PGU, Penza, 2006

[3] Alekhina M. A., Grabovskaya S. M., Asimptoticheski optimalnye po nadezhnosti nevetvyaschiesya programmy s operatorom uslovnoi ostanovki, IITs PGU, Penza, 2013

[4] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 2, 1989, 198–222 | MR | Zbl