|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2013, Number 3, Pages 56–61
(Mi ivm8783)
|
|
|
|
This article is cited in 13 scientific papers (total 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.
Citation:
F. M. Ablayev, K. R. Khadiev, “Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models”, Izv. Vyssh. Uchebn. Zaved. Mat., 2013, no. 3, 56–61; Russian Math. (Iz. VUZ), 57:3 (2013), 46–50
Linking options:
https://www.mathnet.ru/eng/ivm8783 https://www.mathnet.ru/eng/ivm/y2013/i3/p56
|
Statistics & downloads: |
Abstract page: | 251 | Full-text PDF : | 71 | References: | 26 | First page: | 4 |
|