Width Hierarchy for k-OBDD of Small Width

Abstract

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.

8 pages

Cited by in corpus (3)

• Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
• On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
• New Size Hierarchies for Two Way Automata