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.
Similar content being viewed by others
References
Farid Ablayev, Electronic Colloquium on Computational Complexity (ECCC) 21(4) (1997).
Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, and Cristopher Pollette, Inform. Comput. 203(2), 145 (2005).
Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, and Abuzer Yakaryłlmaz, LNCS 8614, 53 (2014).
F. Ablayev and M. Karpinski, ICALP’96 Lecture Notes in Computer Science 1099, 348 (1998).
F. Ablayev and K. Khadiev, Russian Math. 57(3), 46 (2013).
B. Bollig, M. Sauerhoff, D. Sieling, and I. Wegener, Theor. Comput. Sci. 205(1–2), 45 (1998).
A. Borodin, A. Razborov, and R. Smolensky, Comp. Complexity 3(1), 1 (1993).
J. Hromkovic and M. Sauerhoff, 17th STACS (Springer, Berlin, 2000), Vol. 1770, pp. 145–156.
J. Hromkovic and M. Sauerhoff, Theory Comp. Systems 36, 159 (2003).
Kamil Khadiev and Abuzer Yakaryĭlmaz, Sixth Workshop on Non-Classical Models of Automata and Applications (NCMA, 2014), pp. 13–18 (2014).
M. Sauerhoff, Theory Comp. Systems 33, 313 (2000).
J. S. Thathachar, 30th ACM STOC, ACM 653 (1998).
IngoWegener, Branching Programs and Binary Decision Diagrams: Theory and Applications (Society for Industrial and AppliedMathematics, Philadelphia, 2000).
Author information
Authors and Affiliations
Corresponding author
Additional information
Submitted by F. M. Ablayev
Rights and permissions
About this article
Cite this article
Khadiev, K. Width hierarchy for k-OBDD of small width. Lobachevskii J Math 36, 178–183 (2015). https://doi.org/10.1134/S1995080215020092
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080215020092