|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
О максимальных и минимальных элементах частично упорядоченных множеств булевых степеней // Дискретный анализ и исследование операцийстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Марченков С.С.
- Журнал: Дискретный анализ и исследование операций
- Том: 20
- Номер: 2
- Год издания: 2013
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 88
- Последняя страница: 101
- Аннотация: Рассматривается "самый слабый" вариант алгоритмической сводимости - булева сводимость. Исследуются частично упорядоченные множества L_Q булевых степеней, отвечающие различным замкнутым классам Q булевых функций. Доказывается, что для многих замкнутых классов Q соответствующие множества L_Q не имеют максимальных элементов. Приводятся примеры достаточно крупных классов Q, для которых множества L_Q содержат континуальное число максимальных элементов. Устанавливается, что для замкнутых классов T_01, SM соответствующие множества степеней имеют континуальное число минимальных элементов.
- Добавил в систему: Марченков Сергей Серафимович