Geodesic
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

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. 
@article{DM_1992_4_1_a9,
     author = {Yu. G. Tarazevich},
     title = {Realization of a~linear function by plane switching circuits and by circuits on a~plane integral lattice},
     journal = {Diskretnaya Matematika},
     pages = {111--116},
     publisher = {mathdoc},
     volume = {4},
     number = {1},
     year = {1992},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1992_4_1_a9/}
}
TY  - JOUR
AU  - Yu. G. Tarazevich
TI  - Realization of a~linear function by plane switching circuits and by circuits on a~plane integral lattice
JO  - Diskretnaya Matematika
PY  - 1992
SP  - 111
EP  - 116
VL  - 4
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1992_4_1_a9/
LA  - ru
ID  - DM_1992_4_1_a9
ER  - 
%0 Journal Article
%A Yu. G. Tarazevich
%T Realization of a~linear function by plane switching circuits and by circuits on a~plane integral lattice
%J Diskretnaya Matematika
%D 1992
%P 111-116
%V 4
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1992_4_1_a9/
%G ru
%F DM_1992_4_1_a9
Yu. G. Tarazevich. 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. http://geodesic.mathdoc.fr/item/DM_1992_4_1_a9/