Geodesic
Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2015), pp. 47-50 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to realization of parity functions by circuits in the basis $U_\infty$. This basis contains all functions of form $(x_1^{\sigma_1}\&\ldots\& x_k^{\sigma_k})^{\beta}$. We present method of constructing circuts for pairity function of $n$ variables with complexity of $\lfloor (7n-4)/3\rfloor$. This improves previous known upper bound of $U_\infty$-complexity of parity function, that was $\lceil (5n-1)/2\rceil$. It is also shown that constructed circuits are minimal for very small $n$ (for $n<7$). 
@article{VMUMM_2015_5_a9,
     author = {Yu. A. Kombarov},
     title = {Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {47--50},
     year = {2015},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a9/}
}
TY  - JOUR
AU  - Yu. A. Kombarov
TI  - Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2015
SP  - 47
EP  - 50
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a9/
LA  - ru
ID  - VMUMM_2015_5_a9
ER  - 
%0 Journal Article
%A Yu. A. Kombarov
%T Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2015
%P 47-50
%N 5
%U http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a9/
%G ru
%F VMUMM_2015_5_a9
Yu. A. Kombarov. Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 5 (2015), pp. 47-50. http://geodesic.mathdoc.fr/item/VMUMM_2015_5_a9/

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

[2] Redkin N.P., “Dokazatelstvo minimalnosti nekotorykh skhem iz funktsionalnykh elementov”, Problemy kibernetiki, 23, Nauka, M., 1970, 83–101 | MR

[3] Redkin N.P., “O minimalnoi realizatsii lineinoi funktsii skhemoi iz funktsionalnykh elementov”, Kibernetika, 1971, no. 6, 31–38 | MR | Zbl

[4] Kombarov Yu.A., “O minimalnykh skhemakh v bazise Sheffera dlya lineinykh bulevykh funktsii”, Diskretn. analiz i issled. operatsii, 20:4 (2013), 65–87 | MR | Zbl

[5] Schnorr C.P., “Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen”, Computing, 13 (1974), 155–171 | DOI | MR | Zbl

[6] Kombarov Yu.A., “O minimalnykh realizatsiyakh lineinykh bulevykh funktsii”, Diskretn. analiz i issled. operatsii, 19:3 (2012), 39–57 | MR | Zbl

[7] Lai H.Ch., Muroga S., “Logic networks with a minimum number of NOR (NAND) gates for parity functions of $n$ variables”, IEEE Trans. Comput., C-36:2 (1987), 157–166

[8] Wegner I., “The complexity of the parity function in unbounded fan-in, unbounded depth circuits”, Theor. Comput. Sci., 85 (1991), 155–170 | DOI | MR