Geodesic
On the number of bijunctive functions that are invariant under a given permutation
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 23-41 
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/
@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

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

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.

[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