|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О числе максимальных независимых элементов частичных порядков (случай цепей)
Е. В. Дюковаab, Г. О. Масляковb, П. А. Прокофьевc a Федеральный исследовательский центр «Информатика и управление» Российской академии наук
b Московский государственный университет им. М. В. Ломоносова
c Институт машиноведения им. А. А. Благонравова Российской академии наук
Аннотация:
Рассматривается одна из центральных труднорешаемых задач логического анализа данных — дуализация над произведением частичных порядков. Исследуется важный частный случай, когда каждый порядок является цепью. Если мощность каждой цепи равна двум, то рассматриваемая задача — это построение сокращенной дизъюнктивной нормальной формы монотонной булевой функции, заданной конъюнктивной нормальной формой (КНФ), что эквивалентно перечислению неприводимых покрытий булевой матрицы. При условии, что число строк булевой матрицы по порядку меньше числа столбцов, известна асимптотика типичного числа неприводимых покрытий. В настоящей работе аналогичный результат получен для дуализации над произведением цепей, когда мощность каждой цепи больше двух. Получение подобных асимптотических оценок является технически сложной задачей и необходимо, в частности, для обоснования существования асимптотически оптимальных алгоритмов для задачи монотонной дуализации и различных обобщений этой задачи.
Ключевые слова:
задача дуализации, произведение частичных порядков, цепь, покрытие булевой матрицы, упорядоченное покрытие целочисленной матрицы, асимптотически оптимальный алгоритм.
Поступила в редакцию: 15.11.2018
Образец цитирования:
Е. В. Дюкова, Г. О. Масляков, П. А. Прокофьев, “О числе максимальных независимых элементов частичных порядков (случай цепей)”, Информ. и её примен., 13:1 (2019), 25–32
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ia574 https://www.mathnet.ru/rus/ia/v13/i1/p25
|
Статистика просмотров: |
Страница аннотации: | 170 | PDF полного текста: | 58 | Список литературы: | 29 |
|