Geodesic
On the complexity of realizations of Boolean functions in some classes of hypercontact circuits
Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 90-113 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the classes $\operatorname{\text{EM}}_F^{(n)}$ of extended matrices over rings of polynomials with idempotent variables, the following subclasses (hypercontact circuits) are defined: $\operatorname{\text{HC}}_F^{(n)}$ (over an arbitrary field $F$) and $\operatorname{\text{HC}}_Z^{(n)}$ (over the ring of integers), which algebraically extend the class of incident matrices of contact circuits ($\operatorname{\text{CC}}^{(n)}$) and realize arbitrary $n$-place Boolean functions with contact complexity smaller than $3\sqrt{2}\cdot2^{n/2}$. A lower estimate of the same order is obtained for the corresponding Shannon function in the class $\operatorname{\text{HC}}_{F_q}^{(n)}$ over an arbitrary finite field $F_q$. For matrices from the class $\operatorname{\text{HC}}_Z^{(n)}$, we find a physical interpretation in the form of incident-linking matrices of contact-transformer circuits.
Keywords: polynomial with idempotent variables, contact hypergraph, contact matroid, incidence-linking matrix
Mots-clés : hypercontact circuit, contact-transformer circuit. 
@article{DM_2022_34_3_a7,
     author = {Yu. G. Tarazevich},
     title = {On the complexity of realizations of {Boolean} functions in some classes of hypercontact circuits},
     journal = {Diskretnaya Matematika},
     pages = {90--113},
     year = {2022},
     volume = {34},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_3_a7/}
}
TY  - JOUR
AU  - Yu. G. Tarazevich
TI  - On the complexity of realizations of Boolean functions in some classes of hypercontact circuits
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 90
EP  - 113
VL  - 34
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_3_a7/
LA  - ru
ID  - DM_2022_34_3_a7
ER  - 
%0 Journal Article
%A Yu. G. Tarazevich
%T On the complexity of realizations of Boolean functions in some classes of hypercontact circuits
%J Diskretnaya Matematika
%D 2022
%P 90-113
%V 34
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2022_34_3_a7/
%G ru
%F DM_2022_34_3_a7
Yu. G. Tarazevich. On the complexity of realizations of Boolean functions in some classes of hypercontact circuits. Diskretnaya Matematika, Tome 34 (2022) no. 3, pp. 90-113. http://geodesic.mathdoc.fr/item/DM_2022_34_3_a7/

[1] Tarazevich Yu. G., “Rasshirennye polinomialnye matritsy i algebraizatsiya kontaktnykh skhem”, Zhurn. Belorus. gos. un-ta. Matematika. Informatika, 3 (2017), 85–93 | MR

[2] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 2003, 384 pp. | MR

[3] Nigmatullin R. G., Slozhnost bulevykh funktsii, Nauka, M., 1991, 240 pp. | MR

[4] Maltsev A. I., Osnovy lineinoi algebry, Nauka, M., 1970, 402 pp. | MR

[5] Basaker R., Saati T., Konechnye grafy i seti, Nauka, M., 1974, 368 pp. | MR

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

[7] Zarisskii O., Samyuel P., Kommutativnaya algebra, v. 1, IL, M., 1963, 373 pp.

[8] Evnin A. Yu., “Elementarnoe vvedenie v matroidy”, Matem. obr., 2005, no. 2(33), 2–33

[9] Zeifert G., Trelfall V., Topologiya, 2-e izd., Regulyarnaya i khaoticheskaya dinamika, Izhevsk, M., 2001, 448 pp.

[10] Oxley J. G., Matroid Theory, Oxford Univ. Press, New York, 1992, 532 pp. | MR | Zbl

[11] Boltyanskii V. G., Efremovich V. A., Naglyadnaya topologiya, Nauka, M., 1982, 160 pp.

[12] Boltyanskii V. G., Efremovich V. A., “Ocherk osnovnykh idei topologii. (Prodolzhenie)”, Matem. prosv., ser. 2, 4 (1959), 27–52 | Zbl

[13] Boltyanskii V. G., Efremovich V. A., “Ocherk osnovnykh idei topologii. (Okonchanie)”, Matem. prosv., ser. 2, 6 (1961), 107–138 | Zbl

[14] Kasatkin A. S., Nemtsov M. V., Elektrotekhnika, 7-e izd., Vysshaya shkola, M., 2002, 542 pp.

[15] Tarazevich Yu. G., “Algebraicheskii sintez giperkontaktnykh i kontaktno-transformatornykh skhem”, Mater. XIII Mezhdunar. seminara «Diskretnaya matematika i ee prilozheniya», Izd-vo mekh.-matem. f-ta MGU, 2019, 145–148

[16] Tarazevich Yu. G., “Realizatsiya lineinoi funktsii ploskimi kontaktnymi skhemami i skhemami na ploskoi tselochislennoi reshetke”, Diskretnaya matematika, 4:1 (1992), 111–116 | MR | Zbl

[17] Yablonskii S. V., Elementy matematicheskoi kibernetiki, Vysshaya shkola, M., 2007, 188 pp.

[18] Korshunov A. D., “Monotonnye bulevy funktsii”, Uspekhi matem. nauk, 58:5(353) (2003), 89–162 | MR | Zbl