Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models

We consider the well-known k-OBDD branching program model. We propose a technique representing computations in the k-OBDD model as a (described in this paper) automatic communication protocol. This protocol allows us to extend the Bolling–Sauerhoff–Sieling–Wegener hierarchy proved in 1996 for the k-OBDD with constraints on the width. For proving the hierarchy we state and justify a sufficient condition for non-representability of a Boolean function in the k-OBDD. Moreover, using the PJM function (a modification of well-known PJ and ISA functions), we prove a new hierarchy.