Том 9, серия 1, номер 2 , 2002 г., Стр. 36-47
УДК 519.714
Ю. В. Мерекин
Оценки мультипликативной сложности двоичных слов, определяемых поясковыми булевыми функциями
Аннотация:
Для двоичных слов, определяемых поясковыми булевыми функциями, в классе схем конкатенации слов получена асимптотика для мультипликативной сложности, отличная от известной асимптотики для почти всех двоичных слов, определяемых симметрическими булевыми функциями. Получены также асимптотики для мультипликативной сложности слов, определяемых элементарными и монотонными симметрическими булевыми функциями.
Библиогр. 14.
Мерекин Ю. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: merekin@math.nsc.ru
Статья поступила 11 февраля 2002 г.
