Том 7, серия 1, номер 2, 2000 г., Стр. 54-64
УДК 519.714
Ю. В. Мерекин
Нижние оценки сложности символьных последовательностей, определяемых симметрическими булевыми функциями
Аннотация:
Для символьных последовательностей, определяемых классом симметрических булевых функций, в классе схем конкатенации слов получена нижняя оценка сложности, которая для почти всех слов асимптотически совпадает с известной верхней оценкой, а для слов, определяемых симметрическими булевыми функциями, характеристическими последовательностями которых являются последовательности де Брейна, оценка принимает асимптотически максимальное значение.
Библиогр. 5.
Мерекин Ю. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: merekin@math.nsc.ru
Статья поступила 16 декабря 1999 г.
