Geodesic
Improvement of Nonmonotone Complexity Estimates of $k$-Valued Logic Functions
Matematičeskie zametki, Tome 113 (2023) no. 6, pp. 849-862.

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

The problem of determining the nonmonotone complexity of the implementation of $k$-valued logic functions by logic circuits in bases consisting of all monotone (with respect to the standard order) functions and finitely many nonmonotone functions is investigated. In calculating the complexity measure under examination only those elements of the circuit which are assigned nonmonotone basis functions are taken into account. The nonmonotone complexity of an arbitrary $k$-valued logic function is determined with high accuracy, namely, upper and lower bounds which differ by a constant not exceeding $3 \log_2 k+4$ are found.
Keywords: multi-valued logic function, logic circuit, circuit complexity, bases with zero weight elements, nonmonotone complexity, inversion complexity, Markov's theorem. 
@article{MZM_2023_113_6_a5,
     author = {V. V. Kochergin and A. V. Mikhailovich},
     title = {Improvement of {Nonmonotone} {Complexity} {Estimates} of $k${-Valued} {Logic} {Functions}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {849--862},
     publisher = {mathdoc},
     volume = {113},
     number = {6},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2023_113_6_a5/}
}
TY  - JOUR
AU  - V. V. Kochergin
AU  - A. V. Mikhailovich
TI  - Improvement of Nonmonotone Complexity Estimates of $k$-Valued Logic Functions
JO  - Matematičeskie zametki
PY  - 2023
SP  - 849
EP  - 862
VL  - 113
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2023_113_6_a5/
LA  - ru
ID  - MZM_2023_113_6_a5
ER  - 
%0 Journal Article
%A V. V. Kochergin
%A A. V. Mikhailovich
%T Improvement of Nonmonotone Complexity Estimates of $k$-Valued Logic Functions
%J Matematičeskie zametki
%D 2023
%P 849-862
%V 113
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2023_113_6_a5/
%G ru
%F MZM_2023_113_6_a5
V. V. Kochergin; A. V. Mikhailovich. Improvement of Nonmonotone Complexity Estimates of $k$-Valued Logic Functions. Matematičeskie zametki, Tome 113 (2023) no. 6, pp. 849-862. http://geodesic.mathdoc.fr/item/MZM_2023_113_6_a5/

[1] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[2] D. E. Sevidzh, Slozhnost vychislenii, Faktorial, M., 1998 | MR

[3] E. N. Gilbert, “Teoretiko-strukturnye svoistva zamykayuschikh pereklyuchatelnykh funktsii”, Kiberneticheskii sbornik, vyp. 1, IL, M., 1960, 175–188

[4] A. A. Markov, “Ob inversionnoi slozhnosti sistem funktsii”, Dokl. AN SSSR, 116:6 (1957), 917–919 | MR | Zbl

[5] E. I. Nechiporuk, “O slozhnosti skhem v nekotorykh bazisakh, soderzhaschikh netrivialnye elementy s nulevymi vesami”, Problemy kibernetiki, vyp. 8, Fizmatgiz, M., 1962, 123–160 | MR

[6] E. I. Nechiporuk, “O sinteze logicheskikh setei v nepolnykh i vyrozhdennykh bazisakh”, Problemy kibernetiki, vyp. 14, Fizmatgiz, M., 1965, 111–160 | MR

[7] V. V. Kochergin, A. V. Mikhailovich, “Otsenki nemonotonnoi slozhnosti funktsii mnogoznachnoi logiki”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 162{, kniga 3}, Izd-vo Kazanskogo un-ta, Kazan, 2020, 311–321 | DOI

[8] A. A. Markov, “Ob inversionnoi slozhnosti sistemy bulevykh funktsii”, Dokl. AN SSSR, 150:3 (1963), 477–479 | MR | Zbl

[9] V. V. Kochergin, A. V. Mikhailovich, “O minimalnom chisle otritsanii pri realizatsii sistem funktsii mnogoznachnoi logiki”, Diskret. matem., 28:4 (2016), 80–90 | DOI | MR

[10] V. V. Kochergin, A. V. Mikhailovich, “O slozhnosti funktsii mnogoznachnoi logiki v odnom beskonechnom bazise”, Diskretn. analiz i issled. oper., 25:1 (2018), 42–74 | DOI

[11] V. V. Kochergin, A. V. Mikhailovich, “O skhemnoi slozhnosti funktsii $k$-znachnoi logiki v odnom beskonechnom bazise”, Prikladnaya matematika i informatika, 58 (2018), 21–34 | MR

[12] V. V. Kochergin, A. V. Mikhailovich, “Asymptotics of growth for non-monotone complexity of multi-valued logic function systems”, Sib. Èlektron. Mat. Izv., 14 (2017), 1100–1107 | DOI | MR

[13] V. V. Kochergin, A. V. Mikhailovich, “Tochnoe znachenie nemonotonnoi slozhnosti bulevykh funktsii”, Matem. zametki, 105:1 (2019), 32–41 | DOI | MR

[14] S. Jukna, Boolean Function Complexity. Advances and Frontiers, Springer-Verlag, Heidelberg, 2012 | MR