|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Asymptotics of growth for non-monotone complexity of multi-valued logic function systemsстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из списка Web of Science и/или ScopusДата последнего поиска статьи во внешних источниках: 27 марта 2018 г.
- Авторы: Kochergin V.V., Mikhailovich A.V.
- Журнал: Сибирские электронные математические известия
- Том: 14
- Год издания: 2017
- Первая страница: 1100
- Последняя страница: 1107
- DOI: 10.17377/semi.2017.14.093
- Аннотация: The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is finite. In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system $F$ is established. It equals $\lceil\log_{u}(d(F)+1)\rceil - O(1)$. Here $d(F)$ is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system $F$; $u$ is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.
- Добавил в систему: Кочергин Вадим Васильевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | p1100-1107.pdf | 144,1 КБ | 10 ноября 2017 [vvkoch] |