Abstract
In this paper we explore the well-known k-OBDD model of branching programs. We develop a method of representation of the k-OBDD computation process as an “automata-communication protocol” computation process. Our method allows us to extend the hierarchy proved by Bolling-Sauerhoff-Sieling-Wegener in 1996 for k-OBDDs. Moreover, using the PJM function (a modification of well-known PJ and ISA functions), we prove a new hierarchy.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Wegener, Branching Programs and Binary Decision Diagrams: Theory and Applications (Society for Industrial and Applied Mathematics, Philadelphia, 2000).
B. Bolling, M. Sauerhoff, D. Sieling, and I. Wegener, “Hierarchy Theorems for kOBDDs and kIBDDs,” Theoretical Computer Science 205(1–2), 45–60, 1998.
N. Nisan and A. Widgerson, “Rounds In Communication Complexity Revisited,” SIAM Journal on Computing 22(1), 211–219, 1993.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © F.M. Ablayev and K.R. Khadiev, 2013, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2013, No. 3, pp. 56–61.
About this article
Cite this article
Ablayev, F.M., Khadiev, K.R. Extension of the hierarchy for k-OBDDs of small width. Russ Math. 57, 46–50 (2013). https://doi.org/10.3103/S1066369X13030067
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1066369X13030067