RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 1, 2007, том 14, номер 1, страницы 45–69 (Mi da41)  

Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

О глубине булевых функций над произвольным бесконечным базисом

О. М. Касим-Заде

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

Аннотация: Рассматривается реализация булевых функций схемами из функциональных элементов над произвольным бесконечным полным базисом. Под глубиной схемы понимается наибольшее число функциональных элементов, составляющих ориентированную цепь, ведущую от входов схемы к её выходу. Вводится функция Шеннона глубины: при каждом натуральном $n$ её значение $D_B(n)$ равно наименьшей глубине схем, достаточной для реализации над базисом $B$ любой булевой функции от $n$ переменных. Показано, что для любого бесконечного базиса $B$ либо существует константа $\beta\geqslant 1$ такая, что $D_B(n)=\beta$ при всех достаточно больших $n$, либо существуют целочисленная константа $\gamma\geqslant 2$ и константа $\delta$ такие, что $\log_\gamma n\geqslant D_b(n)\geqslant\log_\gamma n+\delta$ при всех $n$.
Библ. 16.

Полный текст: PDF файл (319 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, 2:2, 196–210

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


Образец цитирования: О. М. Касим-Заде, “О глубине булевых функций над произвольным бесконечным базисом”, Дискретн. анализ и исслед. опер., сер. 1, 14:1 (2007), 45–69; J. Appl. Industr. Math., 2:2 (2008), 196–210

Цитирование в формате AMSBIB
\RBibitem{Kas07}
\by О.~М.~Касим-Заде
\paper О глубине булевых функций над произвольным бесконечным базисом
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2007
\vol 14
\issue 1
\pages 45--69
\mathnet{http://mi.mathnet.ru/da41}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2328234}
\zmath{https://zbmath.org/?q=an:1249.94080}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 2
\pages 196--210
\crossref{https://doi.org/10.1134/S1990478908020051}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44849083428}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da41
  • http://mi.mathnet.ru/rus/da/v14/s1/i1/p45

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Кочергин А.В., “О глубине функций $k$-значной логики в бесконечных базисах”, Вестник Московского университета. Серия 1: Математика. Механика, 2011, № 1, 22–26  mathscinet  zmath  elib
    2. О. М. Касим-Заде, “О глубине булевых функций при реализации схемами над произвольным бесконечным базисом”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2012, № 6, 55–57  mathnet  mathscinet; O. M. Kasim-zade, “Depth of Boolean functions realized by circuits over an arbitrary infinite basis”, Moscow University Mathematics Bulletin, 68:1 (2013), 69–70  crossref
    3. А. В. Кочергин, “О глубине функций $k$-значной логики над произвольными базисами”, Фундамент. и прикл. матем., 20:6 (2015), 155–158  mathnet; A. V. Kochergin, “On the depth of $k$-valued logic functions over arbitrary bases”, J. Math. Sci., 233:1 (2018), 100–102  crossref
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:444
    Полный текст:135
    Литература:41
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019