Задача дуализации над произведением цепей: асимптотические оценки числа решений

Рассматривается одна из центральных труднорешаемых задач логического анализа данных – дуализация над произведением частичных порядков. Исследуется важный частный случай, когда каждый порядок является цепью. Если мощность каждой цепи равна двум, то рассматриваемая задача – это построение сокращённой дизъюнктивной нормальной формы монотонной булевой функции, заданной конъюнктивной нормальной формой, что эквивалентно перечислению неприводимых покрытий булевой матрицы. При условии, что число строк булевой матрицы по порядку меньше числа столбцов, известна асимптотика типичного числа неприводимых покрытий. в настоящей работе аналогичный результат получен для дуализации над произведением цепей, когда мощность каждой цепи больше двух. Получение подобных асимптотических оценок является технически сложной задачей и необходимо, в частности, для обоснования существования асимптотически оптимальных алгоритмов для задачи монотонной дуализации и различных обобщений этой задачи.

Ключевые слова

Источник финансирования

Работа выполнена при финансовой поддержке РФФИ (код проекта 16–01–00445).

Получено

17.12.2018

Дата публикации

17.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Дюкова Е. В. , Масляков Г. О. , Прокофьев П. А. Задача дуализации над произведением цепей: асимптотические оценки числа решений // Доклады Академии наук – 2018. – Tом 483. – Номер 2 C. 132-135 [Электронный ресурс]. URL: http://ras.jes.su/dan/s086956520003465-4-1 (дата обращения: 28.04.2024). DOI: 10.31857/S086956520003465-4
MLA	Djukova, E., Maslyakov, E., Prokofjev, P. "The Problem of Dualization over the Product of Chains: Asymptotic Estimates of the Number of Solutions." Doklady Akademii nauk 483.2 (2018):132-135. DOI: 10.31857/S086956520003465-4
APA	Djukova E., Maslyakov E., Prokofjev P. (2018). The Problem of Dualization over the Product of Chains: Asymptotic Estimates of the Number of Solutions. Doklady Akademii nauk 483(2), pp.132-135 DOI: 10.31857/S086956520003465-4

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1303

Оценка читателей: голосов 0

1. Jonson D.S., Yannakakis M., Papadimitriou C.H. // Inform. Processing Letts. 1988. V. 27. P. 119–123.

2. Fredman M.L., Khachiyan L. // J. Algorithms. 1996. V. 21. P. 618–628.

3. Boros E., Elbassioni K., Gurvich V., L. Khachiyan L., K. Makino K. // SIAM J. Comput. 2002. V. 31. № 5. Р. 1624–1643.

4. Дюкова Е. В. // ДАН. 1977. Т. 233. № 4. С. 527–530.

5. Дюкова Е.В., Прокофьев П.А. //ЖВМиМФ. 2015. Т. 55. № 5. С. 895–910.

6. Дюкова Е.В., Масляков Г.О., Прокофьев П.А. // Машинное обучение и анализ данных. 2017. Т. 3. № 4. С. 239–249.

7. Носков В.Н., Слепян В.А. // Кибернетика.1972. №1. С. 60–65.