Geodesic
On length, height and reliability of circuits realizing selection function
Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 108-110.

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

We consider planar (flat) circuits realizing the selection function $v_n=\bigvee_\sigma x_1^{\sigma_1}x_2^{\sigma_2}\dots x_n^{\sigma_n}y_{|\widetilde\sigma|}$, where $n$ is an even integer; $\sigma_i\in\{0,1\}$, $x_i^{\sigma_i}=x_i$ if $\sigma_i=1$ and $x_i^{\sigma_i}=\bar{x_i}$ if $\sigma_i=0$, $i=1,2,\dots,n$; $|\widetilde\sigma|\in\{0,1,\dots,2^n-1\}$ and $|\widetilde\sigma|=\sum_{i=1}^n\sigma_i2^{n-i}$. It is assumed that the switching elements are absolutely reliable, functional elements are subject to inversion failures on its outputs and independently pass into defective states. Some relations for the length and height, as well as an estimate of the unreliability of such circuits are found.
Keywords: Boolean functions, planar circuits, inversion failures, unreliability of circuit, function of selection. 
@article{PDMA_2015_8_a40,
     author = {A. V. Rybakov},
     title = {On length, height and reliability of circuits realizing selection function},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {108--110},
     publisher = {mathdoc},
     number = {8},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2015_8_a40/}
}
TY  - JOUR
AU  - A. V. Rybakov
TI  - On length, height and reliability of circuits realizing selection function
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2015
SP  - 108
EP  - 110
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2015_8_a40/
LA  - ru
ID  - PDMA_2015_8_a40
ER  - 
%0 Journal Article
%A A. V. Rybakov
%T On length, height and reliability of circuits realizing selection function
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2015
%P 108-110
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2015_8_a40/
%G ru
%F PDMA_2015_8_a40
A. V. Rybakov. On length, height and reliability of circuits realizing selection function. Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 108-110. http://geodesic.mathdoc.fr/item/PDMA_2015_8_a40/

[1] Von Neuman J., “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata Studies, eds. C. Shannon, J. Mc. Carthy, Princeton University Press, 1956, 43–98 | MR

[2] Ortyukov S. I., “Ob izbytochnosti realizatsii bulevykh funktsii skhemami iz nenadezhnykh elementov”, Trudy seminara po diskretnoi matematike i eë prilozheniyam (Moskva, 27–29 yanvarya 1987 g.), Izd-vo MGU, M., 1989, 166–168

[3] Uhlig D., “Reliable networks from unreliable gates with almost minimal complexity”, LNCS, 278, 1987, 462–469

[4] Vasin A. V., “Ob asimptoticheski optimalnykh skhemakh v bazise $\{\,\vee,\bar{}\}$ pri inversnykh neispravnostyakh na vykhodakh elementov”, Izvestiya vysshikh uchebnykh zavedenii. Povolzhskii region. Fiziko-matematicheskie nauki, 2008, no. 4, 3–17

[5] Alekhina M. A., Aksenov S. I., “O slozhnosti nadezhnykh skhem pri inversnykh neispravnostyakh”, Materialy IX Mezhdunar. seminara “Diskretnaya matematika i eë prilozheniya”, posvyaschënnogo 75-letiyu so dnya rozhdeniya O. B. Lupanova (Moskva, 18–23 iyunya 2007 g.), Izd-vo mekh.-mat. fak-ta MGU, M., 2007, 56–59

[6] Kravtsov S. S., “O realizatsii funktsii algebry logiki v odnom klasse skhem iz funktsionalnykh i kommutatsionnykh elementov”, Problemy kibernetiki, 19, 1967, 285–292 | Zbl

[7] Ulesova A. Yu., Slozhnost realizatsii bulevykh funktsii v nekotorykh modelyakh kletochnykh skhem, Diplomnaya rabota, MGU im. Lomonosova, fak-t VMiK, kaf. matematicheskoi kibernetiki, M., 2010

[8] Rybakov A. V., “Slozhnost asimptoticheski optimalnykh po nadezhnosti kletochnykh skhem”, Sb. statei KhVIII Mezhdunar. nauch.-metodich. konf. “Universitetskoe obrazovanie”, MKUO-2014 (Penza, 10–11 aprelya 2014 g.), Izd-vo Penz. un-ta, Penza, 2014, 310–311