Geodesic
Maximal groups of invariant transformations of multiaffine, bijunctive, weakly positive, and weakly negative Boolean functions
Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 94-101
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate some properties of multiaffine, bijunctive, weakly positive and weakly negative Boolean functions. The following results are proved: for any integer $k\ge1$ the maximal group of transformations of the domain of definition of a function of $k$ variables with respect to which the set of multiaffine Boolean functions is invariant is the complete affine group $AGL(k,2)$; for the bijunctive functions of $k\ge3$ variables it is the group of transformations each of which is a combination of a permutation and an inversion of the variables of the function; and for a weakly positive (weakly negative) function of $k\ge2$ variables it is the group of transformations each of which is a permutation of the variables of the function. 
@article{DM_2009_21_2_a5,
     author = {S. P. Gorshkov and A. V. Tarasov},
     title = {Maximal groups of invariant transformations of multiaffine, bijunctive, weakly positive, and weakly negative {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {94--101},
     year = {2009},
     volume = {21},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2009_21_2_a5/}
}
TY  - JOUR
AU  - S. P. Gorshkov
AU  - A. V. Tarasov
TI  - Maximal groups of invariant transformations of multiaffine, bijunctive, weakly positive, and weakly negative Boolean functions
JO  - Diskretnaya Matematika
PY  - 2009
SP  - 94
EP  - 101
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2009_21_2_a5/
LA  - ru
ID  - DM_2009_21_2_a5
ER  - 
%0 Journal Article
%A S. P. Gorshkov
%A A. V. Tarasov
%T Maximal groups of invariant transformations of multiaffine, bijunctive, weakly positive, and weakly negative Boolean functions
%J Diskretnaya Matematika
%D 2009
%P 94-101
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2009_21_2_a5/
%G ru
%F DM_2009_21_2_a5
S. P. Gorshkov; A. V. Tarasov. Maximal groups of invariant transformations of multiaffine, bijunctive, weakly positive, and weakly negative Boolean functions. Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 94-101. http://geodesic.mathdoc.fr/item/DM_2009_21_2_a5/

[1] Schaefer T. J., “Complexity of satisfiability problems”, Proc. 10th STOC Conf., ACM Press, 1978, 216–226 | MR

[2] Gorshkov S. P., “Primenenie teorii $NP$-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 325–398

[3] Gizunov S. A., Nosov V. A., “O klassifikatsii vsekh bulevykh funktsii chetyrekh peremennykh po klassam Shefera”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 440–467

[4] Tarasov A. V., “O svoistvakh funktsii, predstavimykh v vide 2-KNF”, Diskretnaya matematika, 13:4 (2001), 99–115 | MR | Zbl

[5] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti bulevykh funktsii”, Obozrenie prikladnoi i promyshlennoi matematiki, 4:2 (1997), 216–237

[6] Pogorelov B. A., “O maksimalnykh podgruppakh simmetricheskikh grupp, zadannykh na proektivnykh prostranstvakh nad konechnym polem”, Matem. zametki, 16:1 (1974), 91–100 | MR | Zbl