On the synthesis of oriented contact circuits with certain restrictions on adjacent contacts

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 _{λ, ν, ω}(n), as the maximum weight of the Boolean function of n variables. For this Shannon function, the so-called high-accuracy bound

$ W_{\lambda ,v,\omega } (n) = \frac{\lambda } {{\lambda - 1}}\frac{{2^n }} {n}\left( {1 + \frac{{\frac{{2\lambda - v - 2}} {{\lambda - 1}}\log n \pm O(1)}} {n}} \right), $ W_{\lambda ,v,\omega } (n) = \frac{\lambda } {{\lambda - 1}}\frac{{2^n }} {n}\left( {1 + \frac{{\frac{{2\lambda - v - 2}} {{\lambda - 1}}\log n \pm O(1)}} {n}} \right),
Keywords:
本文献已被 SpringerLink 等数据库收录！