|
Дискретн. анализ и исслед. опер., сер. 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{https://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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Кочергин А.В., “О глубине функций $k$-значной логики в бесконечных базисах”, Вестник Московского университета. Серия 1: Математика. Механика, 2011, № 1, 22–26
-
О. М. Касим-Заде, “О глубине булевых функций при реализации схемами над произвольным бесконечным базисом”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2012, № 6, 55–57
; 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 -
А. В. Кочергин, “О глубине функций $k$-значной логики над произвольными базисами”, Фундамент. и прикл. матем., 20:6 (2015), 155–158
; A. V. Kochergin, “On the depth of $k$-valued logic functions over arbitrary bases”, J. Math. Sci., 233:1 (2018), 100–102
|
Просмотров: |
Эта страница: | 479 | Полный текст: | 152 | Литература: | 43 |
|