Geodesic
Universal algebras generated by sets of satisfying vectors of bijunctive and $r$-junctive Boolean functions
Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 3, pp. 75-98 
A. V. Tarasov. Universal algebras generated by sets of satisfying vectors of bijunctive and $r$-junctive Boolean functions. Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 3, pp. 75-98. http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a3/
@article{MVK_2011_2_3_a3,
     author = {A. V. Tarasov},
     title = {Universal algebras generated by sets of satisfying vectors of bijunctive and $r$-junctive {Boolean} functions},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {75--98},
     year = {2011},
     volume = {2},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a3/}
}
TY  - JOUR
AU  - A. V. Tarasov
TI  - Universal algebras generated by sets of satisfying vectors of bijunctive and $r$-junctive Boolean functions
JO  - Matematičeskie voprosy kriptografii
PY  - 2011
SP  - 75
EP  - 98
VL  - 2
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a3/
LA  - ru
ID  - MVK_2011_2_3_a3
ER  - 
%0 Journal Article
%A A. V. Tarasov
%T Universal algebras generated by sets of satisfying vectors of bijunctive and $r$-junctive Boolean functions
%J Matematičeskie voprosy kriptografii
%D 2011
%P 75-98
%V 2
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2011_2_3_a3/
%G ru
%F MVK_2011_2_3_a3

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

The notion of universal algebra $\Omega_n^r=(V_n,v_r)$ (where $V_n$ is the set of binary $n$-dimensional vectors and $v_r\colon V_n^{r+1}\to V_n$ is the coordinate-wise operation) is introduced. Subalgebras of this algebra are formed by sets of satisfying vectors for $r$-junctive functions, i.e. functions which may be represented as $r$-CNF. The endomorphisms of these subalgebras of algebra $\Omega_n^r$ and their endomorphic images are described. In the case of $r=2$ several properties of generating systems of the algebra and of some subalgebras are investigated.

[1] Schaefer T., “Complexity of satisfiability problems”, Computing (San Diego, Calif., 1978), ACM, New York, 1978, 216–226 | MR

[2] Gorshkov S. P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozrenie prikl. i promyshl. matem., 2:3 (1995), 325–398 | MR

[3] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti bulevykh funktsii”, Obozrenie prikl. i promyshl. matem., 4:2 (1997), 216–237

[4] Gorshkov S. P., “O peresecheniyakh klassov multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Obozrenie prikl. i promyshl. matem., 4:2 (1997), 238–259

[5] Gorshkov S. P., Tarasov A. V., “Teoretiko-slozhnostnoi podkhod k otsenke slozhnosti resheniya sistem bulevykh uravnenii”, Mater. 4-i Mezhdunar. nauchn. konf. po probl. bezopasn. i protivodeistviya terrorizmu (MaBIT-2008), v. 2, MGU, 2008, 36–45

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

[7] Kon P., Universalnaya algebra, Mir, M., 1968 | MR

[8] Gorshkov S. P., Tarasov A. V., “O maksimalnykh gruppakh invariantnykh preobrazovanii multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Diskretnaya matematika, 21:2 (2009), 94–101 | MR

[9] Sachkov V. N., “Razbieniya s pogloscheniyami i protivorechivye razbieniya mnozhestv”, Trudy po diskretnoi matematike, 4, FIZMATLIT, M., 2001, 201–222

[10] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982 | MR | Zbl