Geodesic
On the structure of one class of perfect $\Pi$-partitions
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 1499-1518.

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

The concept of $\Pi$-partition is an analogue of the concept of normalized formula (a formula in the basis $\{\vee,\wedge,^-\}$ in which negations are possible only over variables) and concept of $\Pi$-schema, just as these last two concepts are analogues of each other. At its core, a $\Pi$-partition is a kind of "imprint" of a formula in the Boolean function calculated by this formula and is considered as a representation of this formula. In order to describe the class of minimal normalized formulas that calculate linear Boolean functions, the structure of the $\Pi$-partitions representing these formulas has been clarified.
Keywords: boolean functions, $\pi$-schemes, normalized formulas, lower bounds on the complexity, formula representation. 
@article{SEMR_2023_20_2_a40,
     author = {K. L. Rychkov},
     title = {On the structure of one class of perfect $\Pi$-partitions},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1499--1518},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a40/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - On the structure of one class of perfect $\Pi$-partitions
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 1499
EP  - 1518
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a40/
LA  - ru
ID  - SEMR_2023_20_2_a40
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T On the structure of one class of perfect $\Pi$-partitions
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 1499-1518
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a40/
%G ru
%F SEMR_2023_20_2_a40
K. L. Rychkov. On the structure of one class of perfect $\Pi$-partitions. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 1499-1518. http://geodesic.mathdoc.fr/item/SEMR_2023_20_2_a40/

[1] V.M. Khrapchenko, “On the complexity of the realization of a linear function in the class of $\Pi$-circuits”, Mat. Zametki, 9:1 (1971), 35–40 | MR | Zbl

[2] K.L. Rychkov, “On the lower bounds for the complexity of serial-parallel contact circuits realizing linear Boolean functions”, Discrete analysis and operations research, Mathematics and its Applications, 355, ed. Korshunov A.D., 1996, 217–234 | MR | Zbl

[3] D.Yu. Cherukhin, “To the question of a logical representation for the parity counter”, Neform. Nauka, 2 (2009), 14–23

[4] K.L. Rychkov, “Lower bounds on the formyla complexity of a linear Boolean function”, Sib. Èlektron. Mat. Izv., 11 (2014), 165–184 | MR | Zbl

[5] K.L. Rychkov, “Complexity of the realization of a linear Boolean function in the class of $\pi$-schemes”, J. Appl. Ind. Math., 12:3 (2018), 540–576 | DOI | MR | Zbl

[6] S.V. Yablonskii, “Realization of a linear function in the class of $\pi$-schemes”, Dokl. Akad. Nauk SSSR, Nov. Ser., 94:5 (1954), 805–806 | MR | Zbl

[7] K.L. Rychkov, “On minimal $\pi$-schemes for linear Boolean functions”, Metody Diskretn. Anal., 51 (1991), 84–104 | MR | Zbl

[8] K.L. Rychkov, “Sufficient conditions for the local repetition-freeness of minimal $\pi$-schemes realizing linear Boolean functions”, J. Appl. Ind. Math., 9:4 (2015), 580–587 | DOI | MR | Zbl

[9] K.L. Rychkov, “On the perfectness of minimal regular partitions of the edge set of the n-dimensional cube”, Diskretn. Anal. Issled. Oper., 26:4 (2019), 74–107 | DOI | MR | Zbl

[10] V.M. Khrapchenko, “On a method of determining lower bounds for the complexity of $\Pi$-schemes”, Mat. Zametki, 10:1 (1971), 83–92 | MR | Zbl

[11] V.M. Khrapchenko, “A simplified proof of a lower complexity estimate”, Discrete Math. Appl., 23:2 (2013), 171–174 | DOI | MR | Zbl

[12] K.L. Rychkov, “Representations of normalized formulas”, Diskretn. Anal. Issled. Oper., 29:4 (2022), 77–103 | DOI | MR | Zbl