Рассматривается задача о сложности и глубине реализации функций многозначной логики формулами и схемами из функциональных элементов над бесконечными неполными базисами. Приводятся примеры бесконечных базисов, допускающих высокие (в том числе сверхэкспоненциальные) нижние оценки сложности.
Скачать электронную версию публикации
Загружен, раз: 405
- Title О нижних оценках сложности функций многозначной логики над бесконечными базисами
- Headline О нижних оценках сложности функций многозначной логики над бесконечными базисами
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(29)
- Date:
- DOI
Ключевые слова
функции многозначной логики, бесконечные базисы, неполные базисы, сверхэкспоненциальные оценки сложности формул, экспоненциальные оценки глубины, functions of multi-valued logic, infinite basises, incomplete basises, over-exponential complexity bounds, exponential depth boundsАвторы
Ссылки
Яблонский С. В. Введение в дискретную математику. М.: Наука, 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.
О нижних оценках сложности функций многозначной логики над бесконечными базисами | Прикладная дискретная математика. 2015. № 3(29).
Скачать полнотекстовую версию
Загружен, раз: 1010