Geodesic
About the reliability of nonbranching programs in the basis of a generalized conjunction
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 33-40 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of synthesis of nonbranching programs with conditional stop-operator is considered in a full finite basis which contains functions of the form $x_1\cdot x_2$, $\overline x_1\cdot x_2$ or $\overline x_1\cdot\overline x_2$. All functional operators are supposed to be prone to output inverse failures with probability $\varepsilon\in(0,1/2)$ and conditional stop-operators are absolutely reliable. Any Boolean function is proved to be realized by a nonbranching program with unreliability no more then $\varepsilon+59\varepsilon^2$ at $\varepsilon\in(0,1/960]$. Ill. 1, bibliogr. 4.
Keywords: Boolean function, nonbranching program, conditional stop-operator, synthesis, reliability. 
@article{DA_2012_19_1_a2,
     author = {S. M. Grabovskaya},
     title = {About the reliability of nonbranching programs in the basis of a~generalized conjunction},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {33--40},
     year = {2012},
     volume = {19},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_1_a2/}
}
TY  - JOUR
AU  - S. M. Grabovskaya
TI  - About the reliability of nonbranching programs in the basis of a generalized conjunction
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 33
EP  - 40
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_1_a2/
LA  - ru
ID  - DA_2012_19_1_a2
ER  - 
%0 Journal Article
%A S. M. Grabovskaya
%T About the reliability of nonbranching programs in the basis of a generalized conjunction
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 33-40
%V 19
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2012_19_1_a2/
%G ru
%F DA_2012_19_1_a2
S. M. Grabovskaya. About the reliability of nonbranching programs in the basis of a generalized conjunction. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 33-40. http://geodesic.mathdoc.fr/item/DA_2012_19_1_a2/

[1] Alekhina M. A., Vasin A. V., “O nadëzhnosti skhem v bazisakh, soderzhaschikh funktsii ne bolee chem trëkh peremennykh”, Uch. zapiski Kazanskogo gos. un-ta. Ser. Fiz.-mat. nauki, 151, no. 2, Izd-vo Kazansk. un-ta, Kazan, 2009, 25–35

[2] Vasin A. V., Asimptoticheski optimalnye po nadëzhnosti skhemy v polnykh bazisakh iz trëkhvkhodovykh elementov, Diss. $\dots$ kand. fiz.-mat. nauk, Penzenskii gos. un-t, Penza, 2010, 100 pp.

[3] Vasin A. V., “Ob asimptoticheski optimalnykh skhemakh v bazise $\{\,\lnot\}$”, Diskret. analiz i issled. operatsii, 16:6 (2009), 12–22 | MR

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