Geodesic
The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity
Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 111-115 
A. A. Voronenko. The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity. Diskretnaya Matematika, Tome 17 (2005) no. 4, pp. 111-115. http://geodesic.mathdoc.fr/item/DM_2005_17_4_a10/
@article{DM_2005_17_4_a10,
     author = {A. A. Voronenko},
     title = {The representability of a {Boolean} function by a repetition-free formula can be verified by a circuit of linear complexity},
     journal = {Diskretnaya Matematika},
     pages = {111--115},
     year = {2005},
     volume = {17},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_4_a10/}
}
TY  - JOUR
AU  - A. A. Voronenko
TI  - The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 111
EP  - 115
VL  - 17
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_4_a10/
LA  - ru
ID  - DM_2005_17_4_a10
ER  - 
%0 Journal Article
%A A. A. Voronenko
%T The representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity
%J Diskretnaya Matematika
%D 2005
%P 111-115
%V 17
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2005_17_4_a10/
%G ru
%F DM_2005_17_4_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

We prove that the representability of a Boolean function by a repetition-free formula can be verified by a circuit of linear complexity. This research was supported by the Russian Foundation for Basic Research, grant 04–01–00359.

[1] Peryazev N. A., “Realizatsiya bulevykh funktsii bespovtornymi formulami”, Diskretnaya matematika, 7:3 (1995), 61–68 | MR | Zbl

[2] Vinokurov S. V., Peryazev N. A., Izbrannye voprosy teorii bulevykh funktsii, Fizmatlit, Moskva, 2001 | Zbl

[3] Voronenko A. A., “O metode razlozheniya dlya raspoznavaniya prinadlezhnosti invariantnym klassam”, Diskretnaya matematika, 14:4 (2002), 110–116 | MR | Zbl

[4] Voronenko A. A., “O proveryayuschikh testakh dlya bespovtornykh funktsii”, Matem. voprosy kibern., 11 (2002), 163–176 | MR