Geodesic
Properties of generator systems of universal algebras generated by Boolean bijunctive functions
Matematičeskie voprosy kriptografii, Tome 3 (2012) no. 2, pp. 117-130 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Two approaches to the description of generator systems of universal algebras generated by Boolean bijunctive functions are considered. Basic sets of these algebras are sets of satisfying vectors of Boolean functions having $2$-CNF form; a ternary operation of these algebras is defined by coordinate-wise application of the voting function to triples of Boolean $n$-dimensional vectors. The first approach is based on the graphs of corresponding $2$-CNF, the second is based on the set cover problem. 
@article{MVK_2012_3_2_a5,
     author = {A. V. Tarasov},
     title = {Properties of generator systems of universal algebras generated by {Boolean} bijunctive functions},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {117--130},
     year = {2012},
     volume = {3},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2012_3_2_a5/}
}
TY  - JOUR
AU  - A. V. Tarasov
TI  - Properties of generator systems of universal algebras generated by Boolean bijunctive functions
JO  - Matematičeskie voprosy kriptografii
PY  - 2012
SP  - 117
EP  - 130
VL  - 3
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2012_3_2_a5/
LA  - ru
ID  - MVK_2012_3_2_a5
ER  - 
%0 Journal Article
%A A. V. Tarasov
%T Properties of generator systems of universal algebras generated by Boolean bijunctive functions
%J Matematičeskie voprosy kriptografii
%D 2012
%P 117-130
%V 3
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2012_3_2_a5/
%G ru
%F MVK_2012_3_2_a5
A. V. Tarasov. Properties of generator systems of universal algebras generated by Boolean bijunctive functions. Matematičeskie voprosy kriptografii, Tome 3 (2012) no. 2, pp. 117-130. http://geodesic.mathdoc.fr/item/MVK_2012_3_2_a5/

[1] Tarasov A. V., “Universalnye algebry, porozhdaemye mnozhestvami vypolnyayuschikh vektorov biyunktivnykh i $r$-yunktivnykh bulevykh funktsii”, Matematicheskie voprosy kriptografii, 2:3 (2011), 75–98

[2] Aspvall B., Plass M. F., Tarjan R. E., “A linear-time algorithm for testing the truth of certain quantified Boolean formulas”, Inform. Process. Lett., 8 (1979), 121–123 | DOI | MR | Zbl

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

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

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

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

[7] Raigorodskii A., Sistemy obschikh predstavitelei i ikh prilozheniya v geometrii, MTsNMO, M., 2006

[8] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, M., 2000, 448 pp. | MR | Zbl

[9] Grettser G., Obschaya teoriya reshetok, Mir, M., 1982, 452 pp. | MR