scientific article; zbMATH DE number 1205991
The article studies properties of a circuit obtained from the function sets \[ \begin{aligned} F&= \{f_1(x_1,x_2,\dots, x_n),\dots, f_n(x_1,x_2,\dots, x_n)\}\\ \text{and} F^{-1}&= \{g_1(x_1,x_2,\dots, x_n),\dots, g_n(x_1,x_2,\dots, x_n)\} \end{aligned} \] using the operators \(B= \{\&,\vee,-\}\). The minimum depth of all the circuits \(S(F)\) defines the depth of the system \(F\) of the base \(B\), which is denoted \(D(F)\). The article proposes a few asymptotic properties for the following quantities: \(D(\Phi)=| D(F)- D(F^{-1})|\) and \(d(n)= \max d(\Phi)\). Based on them, the upper bound problem for \(d(n)\) is completely solved by showing the inequality \(d(n)\geq 2\log_2 n-3\). Finally, the number of the right images \((F=F^{-1})\) are asymptotically evaluated by \(O(2^{n2^{n-1} (1-O(1))})\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4209052)