КФУ. Карточка публикации. Width Hierarchy for k-OBDD of Small Width

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

WIDTH HIERARCHY FOR K-OBDD OF SMALL WIDTH

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

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

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

2015

Язык

английский

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

Хадиев Камиль Равилевич, автор

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

Khadiev Kamil, Width Hierarchy for k-OBDD of Small Width // Electronic Colloquium on Computational Complexity (ECCC) (048), 2015

Аннотация

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.

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

branching program, hierarchy, k-OBDD, OBDD

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

Electronic Colloquium on Computational Complexity

URL

http://eccc.hpi-web.de/report/2015/048/

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

https://repository.kpfu.ru/?p_id=107296

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Хадиев Камиль Равилевич	ru_RU
dc.contributor.author	Хадиев Камиль Равилевич	ru_RU
dc.date.accessioned	2015-01-01T00:00:00Z	ru_RU
dc.date.available	2015-01-01T00:00:00Z	ru_RU
dc.date.issued	2015	ru_RU
dc.identifier.citation	Khadiev Kamil, Width Hierarchy for k-OBDD of Small Width // Electronic Colloquium on Computational Complexity (ECCC) (048), 2015	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/?p_id=107296	ru_RU
dc.description.abstract	Electronic Colloquium on Computational Complexity	ru_RU
dc.description.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.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	branching program	ru_RU
dc.subject	hierarchy	ru_RU
dc.subject	k-OBDD	ru_RU
dc.subject	OBDD	ru_RU
dc.title	Width Hierarchy for k-OBDD of Small Width	ru_RU
dc.type	Статьи в зарубежных журналах и сборниках	ru_RU