|
|
Дискретн. анализ и исслед. опер., 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Merekin Y.V., “Upper bounds for the complexity of sequences generated by symmetric Boolean functions”, Discrete Appl Math, 114:1–3 (2001), 227–231
   -
Ю. В. Мерекин, “Оценки мультипликативной сложности двоичных слов,
определяемых поясковыми булевыми функциями”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 9:2 (2002), 36–47
 -
Ю. В. Мерекин, “О порождении слов с использованием операции композиции”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 10:4 (2003), 70–78
-
В. Н. Потапов, “О максимальной длине двоичных слов с ограниченной частотой единиц и без одинаковых подслов заданной длины”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 11:3 (2004), 48–58
-
Ю. В. Мерекин, “Об аддитивной сложности частично
коммутативных слов”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 12:4 (2005), 40–50
-
Цзюнь Су, “Многоуровневый метод кодирования данных в беспроводных сенсорных сетях”, Электротехнические и компьютерные системы, 2011, № 4, 213–218
 -
Ю. А. Комбаров, “О минимальных схемах в базисе Шеффера для линейных булевых функций”, Дискретн. анализ и исслед. опер., 20:4 (2013), 65–87
-
В. В. Кочергин, “О задачах Беллмана и Кнута и их обобщениях”, Фундамент. и прикл. матем., 20:6 (2015), 159–188 ; V. V. Kochergin, “On Bellman's and Knuth's problems and their generalizations”, J. Math. Sci., 233:1 (2018), 103–124
-
В. В. Кочергин, Д. В. Кочергин, “Уточнение асимптотического поведения сложности сборки слов схемами конкатенации”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2016, № 2, 12–18 ; 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
|
| Просмотров: |
| Эта страница: | 284 | | Полный текст: | 128 | | Первая стр.: | 1 |
|
Пользовательское соглашение