|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О числе максимальных независимых элементов частичных порядков (случай цепей)статья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
- Авторы: Дюкова Е.В., Масляков Г.О., Прокофьев П.А.
- Журнал: Доклады Академии наук
- Том: 483
- Номер: 2
- Год издания: 2018
- Издательство: ФГБУ "Издательство "Наука"
- Местоположение издательства: Москва
- Аннотация: Рассматривается одна из центральных труднорешаемых задач логического анализа данных - дуализация над произведением частичных порядков. Исследуется важный частный случай, когда каждый порядок является цепью. Если мощность каждой цепи равна двум, то рассматриваемая задача – это построение сокращённой дизъюнктивной нормальной формы монотонной булевой функции, заданной конъюнктивной нормальной формой, что эквивалентно перечислению неприводимых покрытий булевой матрицы. При условии, что число строк булевой матрицы по порядку меньше числа столбцов, известна асимптотика типичного числа неприводимых покрытий. В настоящей работе аналогичный результат получен для дуализации над произведением цепей, когда мощность каждой цепи больше двух. Получение подобных асимптотических оценок является технически сложной задачей и необходимо, в частности, для обоснования существования асимптотически оптимальных алгоритмов для задачи монотонной дуализации и различных обобщений этой задачи.
- Добавил в систему: Дюкова Елена Всеволодовна