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/