RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2000, том 7, выпуск 2, страницы 54–64 (Mi da262)

Эта публикация цитируется в 2 статьях

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

Ю. В. Мерекин

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

Аннотация: Для символьных последовательностей, определяемых классом симметрических булевых функций, в классе схем конкатенации слов получена нижняя оценка сложности, которая для почти всех слов асимптотически совпадает с известной верхней оценкой, а для слов, определяемых симметрическими булевыми функциями, характеристическими последовательностями которых являются последовательности де Брейна, оценка принимает асимптотически максимальное значение. Библиогр. 5.

УДК: 519.714

Статья поступила: 16.12.1999



Реферативные базы данных:


© МИАН, 2024