Geodesic
On Complexity of Oriented Contact Circuits with Limited Out-degree
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 164-172 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper studies the implementation of Boolean functions in the class of oriented contact circuits with some restriction on the weight and number of adjacent contacts. Circuits under consideration are those in which out-degree of every vertex is not more than $\lambda$. The weight of vertex is defined as $\lambda$ if its in-degree is one and $\lambda(1+\omega)$, where $\omega>0$, otherwise. Weight of the circuit is sum of weights of its vertices. Weight of Boolean function $f$ is defined as minimal weight of circuit implementing $f$. Shannon function $W_{\lambda,\omega}(n)$ is maximal weight of Boolean function on $n$ input variables. For this function in case when $\lambda>1$ and for any $\omega>0$ we obtain so-called high-accuracy asymptotic bound: $$ W_{\lambda,\omega}(n)=\frac\lambda{\lambda-1}\frac{2^n}n\Biggl(1+\frac{\frac{\lambda-2}{\lambda-1}\log n\pm O(1)}n\Biggr). $$ The results shows how introduction of restrictions on the out-degree of circuit's vertices influences asymptotic behaviour of Shannon function $W_{\lambda,\omega}(n)$ and term $\log n/n$ in its asymptotic expansion. Note that value of $\omega$ influences only on constant in the term $O(1)$.
Keywords: Boolean function, oriented contact circuit, complexity, Shannon function, high-accuracy asymptotic bound. 
@article{UZKU_2009_151_2_a20,
     author = {A. E. Shiganov},
     title = {On {Complexity} of {Oriented} {Contact} {Circuits} with {Limited} {Out-degree}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {164--172},
     year = {2009},
     volume = {151},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a20/}
}
TY  - JOUR
AU  - A. E. Shiganov
TI  - On Complexity of Oriented Contact Circuits with Limited Out-degree
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 164
EP  - 172
VL  - 151
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a20/
LA  - ru
ID  - UZKU_2009_151_2_a20
ER  - 
%0 Journal Article
%A A. E. Shiganov
%T On Complexity of Oriented Contact Circuits with Limited Out-degree
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 164-172
%V 151
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a20/
%G ru
%F UZKU_2009_151_2_a20
A. E. Shiganov. On Complexity of Oriented Contact Circuits with Limited Out-degree. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 164-172. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a20/

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

[2] Lozhkin S. A., Osnovy kibernetiki, Izd-vo Mosk. un-ta, M., 2004, 256 pp.

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

[4] Lupanov O. B., “Ob asimptoticheskikh otsenkakh chisla grafov i setei s $n$ rebrami”, Problemy kibernetiki, 3, Fizmatgiz, M., 1960, 5–21 | MR

[5] Lozhkin S. A., “O sinteze orientirovannykh kontaktnykh skhem”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. i kibernetika, 1995, no. 2, 36–42 | MR | Zbl

[6] Lozhkin S. A., Shiganov A. E., “High accuracy asymptotic bounds on the BDD size and weight of the hardest functions”, Fundamenta Informaticae (to appear)

[7] Korshunov A. D., “Ob asimptoticheskikh otsenkakh slozhnosti kontaktnykh skhem zadannoi stepeni”, Diskr. analiz, 5, Izd-vo In-ta matematiki SO AN SSSR, 1965, 35–63

[8] Lozhkin S. A., “Asimptoticheskie otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov”, Matem. vopr. kibernetiki, 6, Nauka, M., 1996, 189–214 | MR