On lower bounds for complexity over infinite basises for functions of multi-valued logic | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 3(29).

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.

Download file

Counter downloads: 404

Title On lower bounds for complexity over infinite basises for functions of multi-valued logic
Headline On lower bounds for complexity over infinite basises for functions of multi-valued logic
Publesher Tomsk State University
Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(29) 9/2015
Date: 9/2015
DOI

Keywords

функции многозначной логики, бесконечные базисы, неполные базисы, сверхэкспоненциальные оценки сложности формул, экспоненциальные оценки глубины, functions of multi-valued logic, infinite basises, incomplete basises, over-exponential complexity bounds, exponential depth bounds

Authors

Andreev A. A.

Lomonosov Moscow State University

sanchez_14@mail.ru

References

Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 136 c.

Лупанов О. Б. Об одном методе синтеза схем // Изв. вузов. Радиофизика. 1958. Т. 1. № 1. С. 120-140.

Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960. С. 61-80.

Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. Вып. 23. М.: Наука, 1970. С. 43-81.

Касим-Заде О. М. Общая верхняя оценка сложности схем в произвольном бесконечном полном базисе // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 1997. №4. С.59-61.

Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным базисом // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2007. № 1. С. 18-21.

Кочергин А. В. О глубине функций k-значной логики в конечных базисах // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2013. №1. C. 56-59.

Кочергин А. В. О глубине функций k-значной логики в бесконечных базисах // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2011. №1. C. 22-26.

Угольников А. Б. Синтез схем и формул в неполных базисах // Препринт ИПМ АН СССР. М., 1980. №112.

Ткачёв Г. А. О сложности реализации одной последовательности функций k-значной логики // Вестник Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 1977. №1. С. 45-47.

Угольников А. Б. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2004. №3. C.52-55.

Андреев А. А. О нижних оценках сложности для некоторых последовательностей функций многозначной логики // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2013. №6. C. 25-30.

Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. Т. 127. №1. С. 44-46.

Андреев А. А. Об одной последовательности функций многозначной логики // Вестник Моск. ун-та. Сер. 1. Математика. Механика. 2011. №6. C. 52-57.

On lower bounds for complexity over infinite basises for functions of multi-valued logic | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 3(29).

Download full-text version

Counter downloads: 1006