KFU. Card publication. Width Hierarchy for k-OBDD of Small Width

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

WIDTH HIERARCHY FOR K-OBDD OF SMALL WIDTH

Form of presentation

Articles in international journals and collections

Year of publication

2015

Язык

английский

Authors, employees of KFU

Khadiev Kamil Ravilevich, author

Bibliographic description in the original language

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

Annotation

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.

Keywords

branching program, hierarchy, k-OBDD, OBDD

The name of the journal

Electronic Colloquium on Computational Complexity

URL

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

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=107296&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Khadiev Kamil Ravilevich	ru_RU
dc.contributor.author	Khadiev Kamil Ravilevich	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/eng/?p_id=107296&p_lang=2	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	Articles in international journals and collections	ru_RU