Geodesic
Iterated Boolean functions in the elementary basis
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2011), pp. 72-77 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We establish a new criterion for a Boolean function to be read-once over the basis of conjunction, disjunction, and negation. We prove that each Boolean function is either read-once or has a set of four or six input vectors such that values of this function on these vectors show that it is iterated. We use this criterion to deduce an alternative proof of the known Stetsenko criterion.
Keywords: read-once Boolean function, criterion. 
@article{IVM_2011_11_a7,
     author = {A. A. Voronenko and V. S. Fedorova and D. V. Chistikov},
     title = {Iterated {Boolean} functions in the elementary basis},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {72--77},
     year = {2011},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2011_11_a7/}
}
TY  - JOUR
AU  - A. A. Voronenko
AU  - V. S. Fedorova
AU  - D. V. Chistikov
TI  - Iterated Boolean functions in the elementary basis
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2011
SP  - 72
EP  - 77
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/IVM_2011_11_a7/
LA  - ru
ID  - IVM_2011_11_a7
ER  - 
%0 Journal Article
%A A. A. Voronenko
%A V. S. Fedorova
%A D. V. Chistikov
%T Iterated Boolean functions in the elementary basis
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2011
%P 72-77
%N 11
%U http://geodesic.mathdoc.fr/item/IVM_2011_11_a7/
%G ru
%F IVM_2011_11_a7
A. A. Voronenko; V. S. Fedorova; D. V. Chistikov. Iterated Boolean functions in the elementary basis. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2011), pp. 72-77. http://geodesic.mathdoc.fr/item/IVM_2011_11_a7/

[1] Subbotovskaya B. A., “O sravnenii bazisov pri realizatsii funktsii algebry logiki formulami”, DAN SSSR, 149:4 (1963), 784–787 | Zbl

[2] Stetsenko V. A., “O predplokhikh bazisakh v $P_2$”, Matem. vopr. kibernetiki, 4, Fizmatlit, M., 1992, 139–177 | MR

[3] Gurvich V. A., “O bespovtornykh bulevykh funktsiyakh”, UMN, 32:1 (1977), 183–184 | MR | Zbl

[4] Voronenko A. A., “O dline proveryayuschego testa dlya bespovtornykh funktsii v bazise $\{0,1,\,\vee,\neg\}$”, Diskretn. matematika, 17:2 (2005), 139–143 | MR | Zbl

[5] Voronenko A. A., “O proveryayuschikh testakh dlya bespovtornykh funktsii”, Matem. vopr. kibernetiki, 11, Fizmatlit, M., 2002, 163–176 | MR