О схемах из функциональных элементов конечной глубины ветвления

В работе введено понятие глубины ветвления схемы из функциональных элементов и рассмотрены классы схем, имеющие глубину ветвления, ограниченную константой. В данных классах схем и различных базисах получены верхние и нижние оценки сложности линейной булевой функции. Построены бесконечно убывающие последовательности мер сложности при фиксированном базисе и растущей глубине ветвления и при фиксированной глубине ветвления и меняющемся базисе.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 05–01–00994, программой “Университеты России”, грант УР.04.02.528, и программой Президента Российской Федерации поддержки ведущих научных школ, грант НШ 1807.2003.1.