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

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

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



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






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


Дискретн. анализ и исслед. опер., 1996, том 3, номер 1, страницы 52–56 (Mi da427)  

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

Нижняя оценка сложности для схем конкатенации слов

Ю. В. Мерекин

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Приводится метод получения нижних оценок сложности для схем конкатенации слов. В частности, для последовательности де Брейна получена нижняя оценка вида $l/\log_2l$, где $l$ – длина слова. Доказывается, что сложность линейной булевой функции $k$ переменных в этом классе схем равна $2k-1$.
Ил. 1, библиогр. 12

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

Реферативные базы данных:
УДК: 519.714
Статья поступила: 05.01.1996

Образец цитирования: Ю. В. Мерекин, “Нижняя оценка сложности для схем конкатенации слов”, Дискретн. анализ и исслед. опер., 3:1 (1996), 52–56

Цитирование в формате AMSBIB
\RBibitem{Mer96}
\by Ю.~В.~Мерекин
\paper Нижняя оценка сложности для схем конкатенации слов
\jour Дискретн. анализ и исслед. опер.
\yr 1996
\vol 3
\issue 1
\pages 52--56
\mathnet{http://mi.mathnet.ru/da427}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1444681}
\zmath{https://zbmath.org/?q=an:0945.68527}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da427
  • http://mi.mathnet.ru/rus/da/v3/i1/p52

    ОТПРАВИТЬ: 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. Merekin Y.V., “Upper bounds for the complexity of sequences generated by symmetric Boolean functions”, Discrete Appl Math, 114:1–3 (2001), 227–231  crossref  mathscinet  zmath  isi  scopus
    2. Ю. В. Мерекин, “Оценки мультипликативной сложности двоичных слов, определяемых поясковыми булевыми функциями”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 9:2 (2002), 36–47  mathnet  mathscinet  zmath
    3. Ю. В. Мерекин, “О порождении слов с использованием операции композиции”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 10:4 (2003), 70–78  mathnet  mathscinet  zmath
    4. В. Н. Потапов, “О максимальной длине двоичных слов с ограниченной частотой единиц и без одинаковых подслов заданной длины”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 11:3 (2004), 48–58  mathnet  mathscinet
    5. Ю. В. Мерекин, “Об аддитивной сложности частично коммутативных слов”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 12:4 (2005), 40–50  mathnet  mathscinet  zmath
    6. Цзюнь Су, “Многоуровневый метод кодирования данных в беспроводных сенсорных сетях”, Электротехнические и компьютерные системы, 2011, № 4, 213–218  elib
    7. Ю. А. Комбаров, “О минимальных схемах в базисе Шеффера для линейных булевых функций”, Дискретн. анализ и исслед. опер., 20:4 (2013), 65–87  mathnet  mathscinet
    8. В. В. Кочергин, “О задачах Беллмана и Кнута и их обобщениях”, Фундамент. и прикл. матем., 20:6 (2015), 159–188  mathnet; V. V. Kochergin, “On Bellman's and Knuth's problems and their generalizations”, J. Math. Sci., 233:1 (2018), 103–124  crossref
    9. В. В. Кочергин, Д. В. Кочергин, “Уточнение асимптотического поведения сложности сборки слов схемами конкатенации”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2, 12–18  mathnet  mathscinet; V. V. Kochergin, D. V. Kochergin, “Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits”, Moscow University Mathematics Bulletin, 71:2 (2016), 55–60  crossref  isi
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:284
    Полный текст:128
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021