Geodesic
Circuits for disjunction admitting short unitary diagnostic tests
Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 43-54 
S. R. Bedzhanova. Circuits for disjunction admitting short unitary diagnostic tests. Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 43-54. http://geodesic.mathdoc.fr/item/DM_2010_22_4_a3/
@article{DM_2010_22_4_a3,
     author = {S. R. Bedzhanova},
     title = {Circuits for disjunction admitting short unitary diagnostic tests},
     journal = {Diskretnaya Matematika},
     pages = {43--54},
     year = {2010},
     volume = {22},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2010_22_4_a3/}
}
TY  - JOUR
AU  - S. R. Bedzhanova
TI  - Circuits for disjunction admitting short unitary diagnostic tests
JO  - Diskretnaya Matematika
PY  - 2010
SP  - 43
EP  - 54
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2010_22_4_a3/
LA  - ru
ID  - DM_2010_22_4_a3
ER  - 
%0 Journal Article
%A S. R. Bedzhanova
%T Circuits for disjunction admitting short unitary diagnostic tests
%J Diskretnaya Matematika
%D 2010
%P 43-54
%V 22
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2010_22_4_a3/
%G ru
%F DM_2010_22_4_a3

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

We study tests for circuits realising disjunction. In a circuit, the inversion fault is allowed at the output of precisely one functional element. For any functionally complete basis $B$ it is found that for any $n\ge3$ the disjunction of $n$ variables can be realised by a circuit over $B$ which admits a unitary diagnostic test consisting of at most two tuples. It is proved that this result cannot be improved in the general case.

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984

[2] Redkin N. P., Diskretnaya matematika, Izd-vo TsPI pri mekh.-mat. f-te MGU, Moskva, 2007

[3] Redkin N. P., Nadezhnost i diagnostika skhem, Izd-vo MGU, Moskva, 1992

[4] Yablonskii S. V., “Nekotorye voprosy nadezhnosti i kontrolya upravlyayuschikh sistem”, Matematicheskie voprosy kibernetiki, 1, 1988, 5–25 | MR

[5] Redkin N. P., “Edinichnye proveryayuschie testy dlya skhem pri inversnykh neispravnostyakh elementov”, Matematicheskie voprosy kibernetiki, 12, 2003, 217–230

[6] Bedzhanova S. R., “O minimalnykh testakh dlya skhem, realizuyuschikh diz'yunktsiyu”, Diskretnyi analiz i issledovanie operatsii, 15:2 (2008), 3–11 | MR

[7] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986 | MR

[8] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 2, 1992, 198–222