KFU. Card publication. Extension of the hierarchy for k-OBDDs of small width.

EXTENSION OF THE HIERARCHY FOR K-OBDDS OF SMALL WIDTH.

Form of presentation

Articles in international journals and collections

Year of publication

2013

Authors, employees of KFU

Ablaev Farid Mansurovich, 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

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