Width hierarchy for k-OBDD of small width
Kamil Ravilevich Khadiev · Lobachevskii Journal of Mathematics · 2015
In this paper was explored well known model k -OBDD. There are proven width based hierarchy of classes of boolean functions which computed by k -OBDD. The proof of hierarchy is based on sufficient condition of Boolean function’s non representation as k -OBDD and complexity properties of Boolean function SAF. This function is modification of known Pointer Jumping (PJ) and Indirect Storage Access (ISA) functions.