Geodesic
Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 3 (2013), pp. 56-61 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, complexity classes.
Mots-clés : communication protocol 
@article{IVM_2013_3_a5,
     author = {F. M. Ablayev and K. R. Khadiev},
     title = {Clarification of the hierarchy of classes of boolean functions representable as {a~k-OBDD} branching program models},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {56--61},
     year = {2013},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2013_3_a5/}
}
TY  - JOUR
AU  - F. M. Ablayev
AU  - K. R. Khadiev
TI  - Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2013
SP  - 56
EP  - 61
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/IVM_2013_3_a5/
LA  - ru
ID  - IVM_2013_3_a5
ER  - 
%0 Journal Article
%A F. M. Ablayev
%A K. R. Khadiev
%T Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2013
%P 56-61
%N 3
%U http://geodesic.mathdoc.fr/item/IVM_2013_3_a5/
%G ru
%F IVM_2013_3_a5
F. M. Ablayev; K. R. Khadiev. Clarification of the hierarchy of classes of boolean functions representable as a k-OBDD branching program models. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 3 (2013), pp. 56-61. http://geodesic.mathdoc.fr/item/IVM_2013_3_a5/

[1] Wegener I., Branching programs and binary decision diagrams: theory and applications, Society for industrial and applied mathematics, Philadelphia, 2000 | MR | Zbl

[2] Bolling B., Sauerhoff M., Sieling D., Wegener I., “Hierarchy theorems for kOBDDs and kIBDDs”, Theor. Comput. Sci., 205:1–2 (1998), 45–60 | DOI | MR

[3] Nisan N., Widgerson A., “Rounds in communication complexity revisited”, SIAM J. Comput., 22:1 (1993), 211–219 | DOI | MR | Zbl