Geodesic
On the characteristic property of one class of normalized formulas calculating linear Boolean functions
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1522-1548 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

By means of a modification of the method proposed by S. V. Yablonsky for constructing an economical (hypothetically minimal) normalized formula ($\Pi$-circuit) that calculates a given linear Boolean function, a whole class of similar formulas was constructed – the class of so-called optimal perfect normalized formulas. Presumably it is the class of all minimal normalized formulas that compute this function. To prove this conjecture, we consider extending this class to the class of perfect normalized formulas that also compute the same function. It is established that a normalized formula is perfect if and only if it has a perfect representation on the own rectangle of the specified function.
Keywords: Boolean functions, normalized formulas, lower bounds on complexity, formula representations
Mots-clés : $\pi$-circuits, $\Pi$-partitions. 
@article{SEMR_2024_21_2_a30,
     author = {K. L. Rychkov},
     title = {On the characteristic property of one class of normalized formulas calculating linear {Boolean} functions},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1522--1548},
     year = {2024},
     volume = {21},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a30/}
}
TY  - JOUR
AU  - K. L. Rychkov
TI  - On the characteristic property of one class of normalized formulas calculating linear Boolean functions
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 1522
EP  - 1548
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a30/
LA  - ru
ID  - SEMR_2024_21_2_a30
ER  - 
%0 Journal Article
%A K. L. Rychkov
%T On the characteristic property of one class of normalized formulas calculating linear Boolean functions
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 1522-1548
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a30/
%G ru
%F SEMR_2024_21_2_a30
K. L. Rychkov. On the characteristic property of one class of normalized formulas calculating linear Boolean functions. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 1522-1548. http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a30/

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

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

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

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

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

[6] 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 | Zbl

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

[8] K. L. Rychkov, “On the structure of one class of perfect $\Pi$-partitions”, Sib. Èlectron. Mat. Izv., 20:2 (2023), 1499–1518 | DOI | Zbl

[9] Yu.A. Kombarov, “On minimal realizations of linear Boolean functions”, Diskretn. Anal. Issled. Oper., 19:3 (2012), 39–57 | Zbl