Form of presentation | Articles in international journals and collections |
Year of publication | 2013 |
|
Ablaev Farid Mansurovich, author
Khadiev Kamil Ravilevich, author
|
Bibliographic description in the original language |
F. M. Ablayev, K. R. Khadiev.
Extension of the hierarchy for k-OBDDs of small width.
Russian Mathematics.
March 2013, Volume 57, Issue 3, pp 46-50 |
Annotation |
Russian Mathematics |
Keywords |
branching programs, k-OBDD, k-IBDD |
The name of the journal |
Russian Mathematics
|
URL |
http://link.springer.com/article/10.3103/S1066369X13030067# |
Please use this ID to quote from or refer to the card |
https://repository.kpfu.ru/eng/?p_id=61511&p_lang=2 |
Full metadata record ![](https://shelly.kpfu.ru/pdf/picture/arrow_black_right.gif) |
Field DC |
Value |
Language |
dc.contributor.author |
Ablaev Farid Mansurovich |
ru_RU |
dc.contributor.author |
Khadiev Kamil Ravilevich |
ru_RU |
dc.date.accessioned |
2013-01-01T00:00:00Z |
ru_RU |
dc.date.available |
2013-01-01T00:00:00Z |
ru_RU |
dc.date.issued |
2013 |
ru_RU |
dc.identifier.citation |
F. M. Ablayev, K. R. Khadiev.
Extension of the hierarchy for k-OBDDs of small width.
Russian Mathematics.
March 2013, Volume 57, Issue 3, pp 46-50 |
ru_RU |
dc.identifier.uri |
https://repository.kpfu.ru/eng/?p_id=61511&p_lang=2 |
ru_RU |
dc.description.abstract |
Russian Mathematics |
ru_RU |
dc.description.abstract |
Russian Mathematics |
ru_RU |
dc.description.abstract |
We consider deterministic $k\!-\!OBDD$ model of Branching programs. We extend the hierarchy for complexity
classes $\bf k\!-\!OBDD$ of Boolean functions computed by polynomial
size $k\!-\!OBDD$ models of Branching programs of specific width for $ k=o(n/ \log n)$. That is, we prove the following proper
inclusion. For $k = o(n/\log n)$
and $\log^3 n = o(k)$ it holds that
\[ \bf{\frac{k}{\log^2 n}\!-\!OBDD}\subsetneq \bf{k\!-\!OBDD}. \]
The best known result of this kind was proved in 1998 by Bollig, Sauerhoff, Sieling, and Wegener \cite{bssw96} for $k\!-\!OBDD$s for $ k =o(n^{1/2}/\log^{2/3} n)$ length.
|
ru_RU |
dc.language.iso |
ru |
ru_RU |
dc.subject |
branching programs |
ru_RU |
dc.subject |
k-OBDD |
ru_RU |
dc.subject |
k-IBDD |
ru_RU |
dc.title |
Extension of the hierarchy for k-OBDDs of small width.
|
ru_RU |
dc.type |
Articles in international journals and collections |
ru_RU |
|