On the synthesis of oriented contact circuits with certain restrictions on adjacent contacts. (English)
Mosc. Univ. Comput. Math. Cybern. 33, No. 3, 158-166 (2009); translation from Vestn. Mosk. Univ., Ser. XV. 2009, No. 3, 46-52 (2009).
Summary: Realization of Boolean functions in the class of oriented contact circuits (OCCs) with certain restrictions on the weight, number, and types of adjacent contacts is studied. Oriented contact circuits are considered in which, from an arbitrary vertex, at most $λ$ arcs issue and at most $λ$ different Boolean variables are used in the marks of the issuing arcs. The weight of a vertex of an OCC is defined as being equal to $λ$ if one arc enters a vertex and equal to $λ(1+ω)$, where $ω>0$, otherwise. Then, as usual, the weight of an OCC is defined as the sum of the weights of its vertices; the weight of a Boolean function, as the minimum weight of OCCs realizing it; and Shannon function $W_{λ,v,ω}(n)$, as the maximum weight of the Boolean function of $n$ variables. For this Shannon function, the so-called high-accuracy bound $$W_{λ,v,ω}(n)= \fracλ{λ-1} \frac{2^n}{n} \left(1+ \frac{\frac{2λ-v-2} {λ-1} \log n\pm O(1)}{n}\right),$$ which is valid for $λ>1$, $λ>1$, and arbitrary $ω>0$, is obtained. This result shows the influence of the weight and structural restrictions introduced in the class of OCCs on the asymptotic behavior of Shannon function $W_{λ,v,ω}(n)$ and its high-accuracy bounds.