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

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