Geodesic
On implementation of some systems of elementary conjunctions in the class of separating contact circuits
Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 47-60.

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

We show that the system of elementary conjunctions $\Omega_{n,2^k} = {K_0,\ldots,K_{2^{k} -1}}$ such that each conjunction depends essentially on $n$ variables and corresponds to some codeword of a linear $(n, k)$-code can be implemented by a separating contact circuit of complexity at most $2^{k+1} + 4k(n - k) - 2$. We also show that if a contact $(1, 2^k)$-terminal network is separating and implements the system of elementary conjunctions $\Omega_{n,2^k}$, then the number of contacts in it is at least $2^{k+1} - 2$.
Keywords: elementary conjunction, contact circuits, separating circuits, complexity of circuits. 
@article{DM_2021_33_4_a4,
     author = {E. G. Krasulina},
     title = {On implementation of some systems of elementary conjunctions in the class of separating contact circuits},
     journal = {Diskretnaya Matematika},
     pages = {47--60},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_4_a4/}
}
TY  - JOUR
AU  - E. G. Krasulina
TI  - On implementation of some systems of elementary conjunctions in the class of separating contact circuits
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 47
EP  - 60
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_4_a4/
LA  - ru
ID  - DM_2021_33_4_a4
ER  - 
%0 Journal Article
%A E. G. Krasulina
%T On implementation of some systems of elementary conjunctions in the class of separating contact circuits
%J Diskretnaya Matematika
%D 2021
%P 47-60
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_4_a4/
%G ru
%F DM_2021_33_4_a4
E. G. Krasulina. On implementation of some systems of elementary conjunctions in the class of separating contact circuits. Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 47-60. http://geodesic.mathdoc.fr/item/DM_2021_33_4_a4/

[1] Shennon K., “Simvolicheskii analiz releinykh i pereklyuchatelnykh skhem”, Raboty po teorii informatsii i kibernetiki, 1963, 9–45, IL, M.; Shannon C.E., “A symbolic analysis of relay and switching circuits”, Trans. AIEE, 57 (1938), 713–722

[2] Shennon K., “Sintez dvupolyusnykh pereklyuchatelnykh skhem”, Raboty po teorii informatsii i kibernetiki, 28:1 (1963), 59–101, IL., M.

[3] Mur E., “Minimalnye polnostyu dekodiruyuschie kontaktnye skhemy”, Kiberneticheskii sb., 1963, no. 6, 139–152, IL., M.; Moore E.F., “Minimal complete relay decoding networks”, IBM J. Res. Dev., 4:5 (1960), 525–531 | DOI | Zbl

[4] Konig D., Theorie der endlichen and unendlichen Graphen, Chelsea Publishing Company, New York, 1950

[5] Lupanov O.B., “O sinteze kontaktnykh skhem”, DAN SSSR, 119:1 (1958), 23–26 | Zbl

[6] Lupanov O.B., “O sinteze nekotorykh klassov upravlyayuschikh sistem”, Problemy kibernetiki, 10, M., Fizmatgiz, 1963, 63–97

[7] Lupanov O.B., “K voprosu o realizatsii simmetricheskikh funktsii algebry logiki kontaktnymi skhemami”, Problemy kibernetiki, 15, Nauka, M., 1965, 85–99

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

[9] Nechiporuk E.I., “O topologicheskikh printsipakh samokorrektirovaniya”, Problemy kibernetiki, 21, Nauka, M., 1969, 5–102

[10] Redkin N.P., “O realizatsii sistem kon'yunktsii kontaktnymi skhemami”, Problemy kibernetiki, 30, Nauka, M., 1975, 263–276

[11] Andreev A.E., “Universalnyi printsip samokorrektirovaniya”, Matem. sb., 127(169):2(6) (1985), 147–172 ; Andreev A.E., “A universal principle of self-correction”, Math. USSR-Sb., 55:1 (1986), 145–169 | MR | Zbl | DOI

[12] Vikhlyantsev I.A., “O realizatsii sistem kon'yunktsii kontaktnymi skhemami”, Diskretnaya matematika, 1:4 (1989), 3–11 | Zbl

[13] Krasulina E.G., “O nizhnei otsenke slozhnosti realizatsii sistemy vsekh elementarnykh simmetricheskikh funktsii kontaktnymi skhemami”, Matematicheskie voprosy kibernetiki, 19, Fizmatgiz, M., 2019, 113–122

[14] Piterson U., Ueldon E., Kody, ispravlyayuschie oshibki, Mir, M., 1976; Peterson W.W., Weldon E.J., Error-correcting codes, MIT Press, 1972