Geodesic
On lower bounds for complexity over infinite basises for functions of multi-valued logic
Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 5-16.

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

The complexity and the depth of multi-valued logic functions realization by formulas and by circuits of functional gates over infinite incomplete basises are estimated. Some examples of infinite basises allowing high (including overexponential) lower bounds for complexity are presented.
Keywords: functions of multi-valued logic, infinite basises, incomplete basises, overexponential complexity bounds, exponential depth bounds. 
@article{PDM_2015_3_a0,
     author = {A. A. Andreev},
     title = {On lower bounds for complexity over infinite basises for functions of multi-valued logic},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--16},
     publisher = {mathdoc},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_3_a0/}
}
TY  - JOUR
AU  - A. A. Andreev
TI  - On lower bounds for complexity over infinite basises for functions of multi-valued logic
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 5
EP  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_3_a0/
LA  - ru
ID  - PDM_2015_3_a0
ER  - 
%0 Journal Article
%A A. A. Andreev
%T On lower bounds for complexity over infinite basises for functions of multi-valued logic
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 5-16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_3_a0/
%G ru
%F PDM_2015_3_a0
A. A. Andreev. On lower bounds for complexity over infinite basises for functions of multi-valued logic. Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 5-16. http://geodesic.mathdoc.fr/item/PDM_2015_3_a0/

[1] Yablonskiy S. V., Introduction to Discrete Mathematics, Nauka Publ., Moscow, 1986, 384 pp. (in Russian) | MR

[2] Lupanov O. B., Asymptotic Bounds for the Complexity of Control Systems, MSU Publ., Moscow, 1984, 136 pp. (in Russian)

[3] Lupanov O. B., “A method of circuits synthesis”, Izvestiya vuzov. Radiofizika, 1:1 (1958), 120–140 (in Russian)

[4] Lupanov O. B., “On the complexity of Boolean functions realization by formulas”, Problemy kibernetiki, 3, Fizmatgiz Publ., Moscow, 1960, 61–80 (in Russian) | MR

[5] Lupanov O. B., “On circuits of functional elements with delays”, Problemy kibernetiki, 23, Nauka Publ., Moscow, 1970, 43–81 (in Russian) | MR

[6] Kasim-Zade O. M., “Total upper bound for the circuits complexity in any infinite complete basis”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 1997, no. 4, 59–61 (in Russian) | MR | Zbl

[7] Kasim-Zade O. M., “The depth of Boolean functions realized by circuits over an arbitrary basis”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2007, no. 1, 18–21 (in Russian) | MR | Zbl

[8] Kochergin A. V., “Depth of $k$-valued logic functions in finite bases”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2013, no. 1, 56–59 (in Russian) | MR | Zbl

[9] Kochergin A. V., “Depth of $k$-valued logic functions in infinite bases”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2011, no. 1, 22–26 (in Russian) | MR | Zbl

[10] Ugol'nikov A. B., The circuits and formulas synthesis in incomplete bases, Preprint No 112, Keldysh Institute of Applied Mathematics, Moscow, 1980 (in Russian) | MR

[11] Tkachev G. A., “On the complexity of a sequence of $k$-ary functions realization”, Vestnik Mosk. un-ta. Ser. 15. Vychislitel'naya matematika i kibernetika, 1977, no. 1, 45–47 (in Russian)

[12] Ugol'nikov A. B., “On the complexity of one sequence of $4$-ary functions realization by formulas”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2004, no. 3, 52–55 (in Russian) | MR | Zbl

[13] Andreev A. A., “Lower complexity estimates for some sequences of functions of multivalued logic”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2013, no. 6, 25–30 (in Russian) | Zbl

[14] Yanov Yu. I., Muchnik A. A., “On the existence of $k$-valued closed classes without a finite basis”, Reports of the USSR Academy of Sciences, 127:1 (1959), 44–46 (in Russian) | Zbl

[15] Andreev A. A., “A sequence of functions of the multi-valued logic”, Vestnik Mosk. un-ta. Ser. 1. Matematika. Mekhanika, 2011, no. 6, 52–57 (in Russian) | MR | Zbl