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

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

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


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




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

Дискретный анализ и исследование операций, сер. 1, 2007, том 14, выпуск 3, страницы 31–39 (Mi da204)  
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

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

А. В. Васильев

Казанский государственный университет
PDF полного текста (231 kB) Список цитирования (2)
Список литературы:
PDF
HTML
Аннотация: Дэвид М. Баррингтон доказал совпадение класса функций, реализуемых схемами из функциональных элементов логарифмической глубины NC$^1$, с классом функций, представимых ветвящимися программами константной ширины и полиномиальной длины BWBP.
В статье уточняется структура ветвящихся программ, получаемых предложенным Баррингтоном методом. А именно, доказывается, что с помощью $k$-OBDD полиномиальной сложности и ширины 5 можно реализовать все функции из класса NC$^1$ и только их. Это утверждение можно переформулировать следующим образом: poly$(n)$-OBDD$_5$ = NC$^1$.
Библ. 4.
Статья поступила: 20.10.2006
Переработанный вариант: 18.05.2007
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2008, Volume 2, Issue 4, Pages 585–590
DOI: https://doi.org/10.1134/S1990478908040145
Реферативные базы данных:
УДК: 519.85
Образец цитирования: А. В. Васильев, “О функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида”, Дискретн. анализ и исслед. опер., сер. 1, 14:3 (2007), 31–39; J. Appl. Industr. Math., 2:4 (2008), 585–590
Цитирование в формате AMSBIB
\RBibitem{Vas07}
\by А.~В.~Васильев
\paper О~функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2007
\vol 14
\issue 3
\pages 31--39
\mathnet{http://mi.mathnet.ru/da204}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2391916}
\zmath{https://zbmath.org/?q=an:1249.68079}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 4
\pages 585--590
\crossref{https://doi.org/10.1134/S1990478908040145}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-57549111000}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da204
  • https://www.mathnet.ru/rus/da/v14/s1/i3/p31
    • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:406
    PDF полного текста:134
    Список литературы:44
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024