This article is cited in 13 papers

Brief communications

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

F. M. Ablayev, K. R. Khadiev

Chair of Theoretical Cybernetics, Kazan (Volga Region) Federal University, Kazan, Russia

Abstract: 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.

Keywords: branching program, OBDD, k-OBDD, communication protocol, complexity classes.

UDC: 519.7

Presented by the member of Editorial Board: N. K. Zamov
Received: 05.07.2012

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2013, 57:3, 46–50

Bibliographic databases:

•