Эта публикация цитируется в
2 статьях
Краткие сообщения
Обобщение оценок мощности плоских схем, реализующих частичные булевы операторы
Г. В. Калачев Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
В статье исследуется порядок функции Шеннона потенциала (активности) плоских схем, реализующих частичные булевы операторы при наличии ограничения на количество различных значений, принимаемых оператором. Показано, что для класса частичных операторов с
$m$ выходами, областью определения мощности
$d$ и областью значений мощности не более
$r$ как средняя, так и максимальная мощности по порядку равны
$(\sqrt{d}+m\sqrt{r}/\log r)\sqrt{\log r}$ при незначительных ограничениях на параметры.
Ключевые слова:
клеточные схемы, активность, потенциал, функция Шеннона, нижние оценки, верхние оценки, булевы операторы.
УДК:
519.714 Поступила в редакцию: 27.09.2017