КФУ. Карточка публикации. Extension of the hierarchy for k-OBDDs of small width.

RUS

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

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2013

Авторы, сотрудники КФУ

Аблаев Фарид Мансурович, автор

Библиографическое описание на языке оригинала

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

Аннотация

Russian Mathematics

Ключевые слова

branching programs, k-OBDD, k-IBDD

Название журнала

Russian Mathematics

URL

http://link.springer.com/article/10.3103/S1066369X13030067#

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

Поле DC	Значение	Язык
dc.contributor.author	Аблаев Фарид Мансурович	ru_RU
dc.contributor.author	Хадиев Камиль Равилевич	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/?p_id=61511	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	Статьи в зарубежных журналах и сборниках	ru_RU