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/}
}
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/