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

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

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



Вестн. Моск. ун-та. Сер. 1. Матем., мех.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1994, номер 6, страницы 40–44 (Mi vmumm2305)  

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

Математика

О сложности схем в одном бесконечном базисе

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


Аннотация: Исследуется реализация булевых функций схемами из функциональных элементов в бесконечном базисе антицепных функций. Показано, что для реализации любой функции от $n$ переменных схемой в рассматриваемом базисе достаточно $n+1$ элементов в бесконечном базисе антицепных функций. Показано, что для реализации любой от $n$ переменных требуется по порядку не менее $n^{1/3}$ элементов.
Библиогр. 2.

Полный текст: PDF файл (682 kB)

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.95
Поступила в редакцию: 15.06.1994

Образец цитирования: О. М. Касим-Заде, “О сложности схем в одном бесконечном базисе”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1994, № 6, 40–44

Цитирование в формате AMSBIB
\RBibitem{Kas94}
\by О.~М.~Касим-Заде
\paper О сложности схем в одном бесконечном базисе
\jour Вестн. Моск. ун-та. Сер.~1. Матем., мех.
\yr 1994
\issue 6
\pages 40--44
\mathnet{http://mi.mathnet.ru/vmumm2305}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1373187}
\zmath{https://zbmath.org/?q=an:0874.94047}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vmumm2305
  • http://mi.mathnet.ru/rus/vmumm/y1994/i6/p40

    ОТПРАВИТЬ: 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. О. М. Касим-Заде, “Об одном методе получения оценок сложности схем над произвольным бесконечным базисом”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 11:2 (2004), 41–65  mathnet  mathscinet  zmath
    2. О. В. Подольская, “О нижних оценках сложности схем в базисе антицепных функций”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2013, № 2, 17–23  mathnet  mathscinet; O. V. Podolskaya, “Lower estimates of circuit complexity in the basis of antichain functions”, Moscow University Mathematics Bulletin, 68:2 (2013), 98–103  crossref
    3. О. В. Подольская, “Сложность реализации симметрических булевых функций схемами в базисе антицепных функций”, Дискрет. матем., 27:3 (2015), 95–107  mathnet  crossref  mathscinet  elib; Olga V. Podolskaya, “Circuit complexity of symmetric Boolean functions in antichain basis”, Discrete Math. Appl., 26:1 (2016), 31–39  crossref  isi
    4. О. В. Подольская, “Сложность линейных функций и функции голосования в базисе антицепных функций”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2, 51–52  mathnet  mathscinet; O. V. Podolskaya, “Complexity of linear and majority functions in the basis of antichain functions”, Moscow University Mathematics Bulletin, 71:2 (2016), 82–83  crossref  isi
    5. В. В. Кочергин, А. В. Михайлович, “О сложности функций многозначной логики в одном бесконечном базисе”, Дискретн. анализ и исслед. опер., 25:1 (2018), 42–74  mathnet  crossref  elib; V. V. Kochergin, A. V. Mikhailovich, “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Industr. Math., 12:1 (2018), 40–58  crossref
  • Просмотров:
    Эта страница:5
    Полный текст:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020