УДК 519.714

Обобщение оценок мощности плоских схем, реализующих частичные булевы операторы / Г. В. Калачев. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2018. № 3. С. 60-64.

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

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

Библиогр. 12.