Realization of a linear function by plane switching circuits and by circuits on a plane integral lattice
Diskretnaya Matematika, Tome 4 (1992) no. 1, pp. 111-116
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
We consider a problem of the realization of a linear Boolean function by plane switching circuits and switching-conducting circuits on a plane integral lattice. It is well known [O. B. Lupanov, Asymptotic estimates for the complexity of control systems (Russian), Moskov. Gos. Univ., 1984; per bibl.] that a linear function is realized with linear complexity in the class of arbitrary switching circuits and with quadratic complexity in the class of $\pi$-circuits. Here we obtain a linear upper bound on complexity of a linear function in the class of plane switching circuits and an upper bound of the form $n^{1+\varepsilon (n)}$ for complexity of the same function in the class of circuits on a plane integral lattice.