RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2018, номер 3, страницы 60–64 (Mi vmumm35)

Эта публикация цитируется в 2 статьях

Краткие сообщения

Обобщение оценок мощности плоских схем, реализующих частичные булевы операторы

Г. В. Калачев

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В статье исследуется порядок функции Шеннона потенциала (активности) плоских схем, реализующих частичные булевы операторы при наличии ограничения на количество различных значений, принимаемых оператором. Показано, что для класса частичных операторов с $m$ выходами, областью определения мощности $d$ и областью значений мощности не более $r$ как средняя, так и максимальная мощности по порядку равны $(\sqrt{d}+m\sqrt{r}/\log r)\sqrt{\log r}$ при незначительных ограничениях на параметры.

Ключевые слова: клеточные схемы, активность, потенциал, функция Шеннона, нижние оценки, верхние оценки, булевы операторы.

УДК: 519.714

Поступила в редакцию: 27.09.2017


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2018, 73:3, 120–123

Реферативные базы данных:


© МИАН, 2024