Geodesic
On a~wide class of bases with unreliability coefficient equal to one
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 1, pp. 5-18.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B$. We assume that all elements are subjected independently of each other to inverse failures on the output with probability $\varepsilon\in(0,1/2)$. We find a set of functions $G$ and prove that the unreliability coefficient of the basis $B$ which contains functions of $G$ equals 1. Ill. 3, bibliogr. 13.
Keywords: unreliable functional element, circuit asymptotically optimal with respect to reliability, inverse failure on outputs of elements, synthesis of circuits composed of unreliable elements. 
@article{DA_2015_22_1_a0,
     author = {A. V. Vasin},
     title = {On a~wide class of bases with unreliability coefficient equal to one},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--18},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_1_a0/}
}
TY  - JOUR
AU  - A. V. Vasin
TI  - On a~wide class of bases with unreliability coefficient equal to one
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 18
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_1_a0/
LA  - ru
ID  - DA_2015_22_1_a0
ER  - 
%0 Journal Article
%A A. V. Vasin
%T On a~wide class of bases with unreliability coefficient equal to one
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-18
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_1_a0/
%G ru
%F DA_2015_22_1_a0
A. V. Vasin. On a~wide class of bases with unreliability coefficient equal to one. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 1, pp. 5-18. http://geodesic.mathdoc.fr/item/DA_2015_22_1_a0/

[1] S. I. Aksenov, “On reliability of circuits over an arbitrary complete system of functions under inverse failures at the element outputs”, Izv. VUZ. Povolzh. Reg., Ser. Estestv. Nauki, 2005, no. 6, 42–55

[2] V. B. Alekseev, Lectures on Discrete Mathematics, Izdatel'skii Otd. Fak. VMiK MGU, Moscow, 2004

[3] M. A. Alekhina, Synthesis of Asymptotically Optimal Reliable Circuits from Unreliable Elements, Inf.-Izdatel'skii Tsentr PGU, Penza, 2006

[4] M. A. Alekhina, S. I. Aksenov, A. V. Vasin, “On functions and circuits used to improve reliability of circuits”, Izv. VUZ. Povolzh. Reg., Ser. Fiz.-Mat. Nauki, 2008, no. 3, 30–38

[5] M. A. Alekhina, A. V. Vasin, “On reliability of combinatorial circuits in bases containing functions with at most three variables”, Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauki, 151, no. 2, 2009, 25–35 | Zbl

[6] A. V. Vasin, “On functions of a special form”, Proc. VIII Int. Conferentsii “Discrete Models in the Theory of Control Systems” (Lesnoi gorodok, Moscow Reg., Russia, Apr. 6–9, 2009), MAKS Press, Moscow, 2009, 43–46

[7] A. V. Vasin, “On asymptotically optimal circuits in the base $\{\,\lnot\}$ under inverse failures at the element outputs”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 12–22 | MR | Zbl

[8] O. B. Lupanov, Asymptotic Bounds on Complexity of Control Systems, Izdatel'stvo MGU, Moscow, 1984

[9] J. von Neumann, “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata Studies, eds. C. E. Shannon, J. McCarthy, Princeton Univ. Press, Princeton, NJ, 1956, 43–98 | MR

[10] S. I. Ortyukov, “On redundancy of Boolean function realization with circuits of unreliable elements”, Proc. Seminar on Discrete Mathematics and its Applications (Moscow, Russia, Jan. 27–29, 1987), Izdatel'stvo MGU, Moscow, 1989, 166–168

[11] V. V. Chugunova, Synthesis of asymptotically optimal reliable circuits under inverse failures at the element outputs, Cand. Sci. Dissertation, Penz. Gos. Univ., Penza, 2007

[12] S. V. Yablonskii, “Asymptotically best method for synthesis of reliable circuits from unreliable elements”, Discrete Mathematics, Banach Cent. Publ., 7, eds. J. L. Kulikowski, M. Michalewicz, S. V. Yablonskii, Yu. I. Zhuravlev, Instytut Matematyczny PAN, Warsaw, 1982, 11–19 | MR

[13] Uhlig D., “Reliable networks from unreliable gates with almost minimal comlexity”, Fundamentals of Computation Theory, Proc. Int. Conf. FCT'87 (Kazan, June, 1987), Lect. Notes Comput. Sci., 278, Springer-Verl., Berlin, 1987, 462–469 | DOI