RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Информ. и её примен.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Информ. и её примен., 2019, том 13, выпуск 1, страницы 25–32 (Mi ia574)  

О числе максимальных независимых элементов частичных порядков (случай цепей)

Е. В. Дюковаab, Г. О. Масляковb, П. А. Прокофьевc

a Федеральный исследовательский центр «Информатика и управление» Российской академии наук
b Московский государственный университет им. М. В. Ломоносова
c Институт машиноведения им. А. А. Благонравова Российской академии наук

Аннотация: Рассматривается одна из центральных труднорешаемых задач логического анализа данных — дуализация над произведением частичных порядков. Исследуется важный частный случай, когда каждый порядок является цепью. Если мощность каждой цепи равна двум, то рассматриваемая задача — это построение сокращенной дизъюнктивной нормальной формы монотонной булевой функции, заданной конъюнктивной нормальной формой (КНФ), что эквивалентно перечислению неприводимых покрытий булевой матрицы. При условии, что число строк булевой матрицы по порядку меньше числа столбцов, известна асимптотика типичного числа неприводимых покрытий. В настоящей работе аналогичный результат получен для дуализации над произведением цепей, когда мощность каждой цепи больше двух. Получение подобных асимптотических оценок является технически сложной задачей и необходимо, в частности, для обоснования существования асимптотически оптимальных алгоритмов для задачи монотонной дуализации и различных обобщений этой задачи.

Ключевые слова: задача дуализации, произведение частичных порядков, цепь, покрытие булевой матрицы, упорядоченное покрытие целочисленной матрицы, асимптотически оптимальный алгоритм.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 19-01-00430_а
Работа выполнена при частичной финансовой поддержке РФФИ (проект 19-01-00430-а).


DOI: https://doi.org/10.14357/19922264190104

Полный текст: PDF файл (188 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
Поступила в редакцию: 15.11.2018

Образец цитирования: Е. В. Дюкова, Г. О. Масляков, П. А. Прокофьев, “О числе максимальных независимых элементов частичных порядков (случай цепей)”, Информ. и её примен., 13:1 (2019), 25–32

Цитирование в формате AMSBIB
\RBibitem{DyuMasPro19}
\by Е.~В.~Дюкова, Г.~О.~Масляков, П.~А.~Прокофьев
\paper О числе максимальных независимых элементов частичных порядков (случай цепей)
\jour Информ. и её примен.
\yr 2019
\vol 13
\issue 1
\pages 25--32
\mathnet{http://mi.mathnet.ru/ia574}
\crossref{https://doi.org/10.14357/19922264190104}
\elib{http://elibrary.ru/item.asp?id=37170979}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ia574
  • http://mi.mathnet.ru/rus/ia/v13/i1/p25

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Информатика и её применения
    Просмотров:
    Эта страница:54
    Полный текст:23
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020