High-accuracy asymptotic bounds for the realization complexity of function systems by iterative contact circuits

We investigate the realization complexity of systems of Boolean functions in the class of iterative contact circuits - an extension of the class of contact circuits. The objective is to obtain so-called high-accuracy asymptotic bounds for the Shannon function L ICC (n,m), which describe the asymptotic behavior of both the Shannon function and the first residual term in its asymptotic expansion. We show that for m < 22(n-1)/2 - n we have the bound LICC (n,m) = m·2n - 1/n + logm (1 + 5log(n + logm)/2(n + logm) + O(1/n + logm)). The problem is thus solved with a fairly weak constraint on the number of functions. © 2006 Springer Science+Business Media, Inc.