Geodesic
On the number of bijunctive functions that are invariant under a given permutation
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 23-41
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The class of Boolean bijunctive functions is one of the Sheffer classes. The main property which makes investigations of bijunctive functions important is the property that the problem of testing the consistency of a system of equations over a Sheffer class of functions is of a polynomial complexity (see, for example, [1–4]). In this paper, we estimate the number of bijunctive functions containing a given permutation in their inertia groups with respect to the symmetric group. In particular, we describe properties and find the number of bijunctive functions invariant with respect to a unicyclic permutation of the variables. 
@article{DM_2002_14_3_a3,
     author = {P. V. Roldugin and A. V. Tarasov},
     title = {On the number of bijunctive functions that are invariant under a given permutation},
     journal = {Diskretnaya Matematika},
     pages = {23--41},
     year = {2002},
     volume = {14},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_3_a3/}
}
TY  - JOUR
AU  - P. V. Roldugin
AU  - A. V. Tarasov
TI  - On the number of bijunctive functions that are invariant under a given permutation
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 23
EP  - 41
VL  - 14
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_3_a3/
LA  - ru
ID  - DM_2002_14_3_a3
ER  - 
%0 Journal Article
%A P. V. Roldugin
%A A. V. Tarasov
%T On the number of bijunctive functions that are invariant under a given permutation
%J Diskretnaya Matematika
%D 2002
%P 23-41
%V 14
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2002_14_3_a3/
%G ru
%F DM_2002_14_3_a3
P. V. Roldugin; A. V. Tarasov. On the number of bijunctive functions that are invariant under a given permutation. Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 23-41. http://geodesic.mathdoc.fr/item/DM_2002_14_3_a3/

[1] Schaefer T., “Complexity of satisfiability problems”, Proc. 10 Annual ACM Symp. on Theory of Computing, 1978, 216–226 | MR

[2] Dantsin E. Ya., “Algoritmika zadachi vypolnimosti”, Voprosy kibern., 131 (1987), 7–21 | MR

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

[4] Gorshkov S. P., “O slozhnosti zadachi nakhozhdeniya chisla reshenii sistem bulevykh uravnenii”, Diskretnaya matematika, 8:1 (1996), 72–85 | MR

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

[6] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1997 | MR

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