Уточнение иерархии класса булевых функций, представимых в моделях k-OBDD ветвящихся программ

В статье рассматривается известная модель ветвящихся программ – k-OBDD. Нами разработан метод представления процесса вычисления в k-OBDD в виде (определяемого в работе) автоматного коммуникационного протокола, который позволяет продолжить иерархию Bolling–Sauerhoff–Sieling–Wegener, доказанную в 1996 году для k-OBDD с ограничениями на ширину. Для доказательства иерархии было определено и доказано достаточное условие непредставимости булевой функции в k-OBDD. А также, на основе функции PJM, модификации известных функций РJ и ISA, доказана новая иерархия.