|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Об m-юнктивных предикатах на конечном множествестатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКДата последнего поиска статьи во внешних источниках: 24 января 2020 г.
- Автор: Селезнева С.Н.
- Журнал: Дискретный анализ и исследование операций
- Том: 26
- Номер: 3
- Год издания: 2019
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 46
- Последняя страница: 59
- DOI: 10.33048/daio.2019.26.647
- Аннотация: Рассматриваются предикаты на конечных множествах. Предикаты, инвариантные относительно некоторой (m+1)-местной функции почти единогласия, названы m-юнктивными. Предлагается представление предикатов на конечном множестве в виде обобщённых конъюнктивных нормальных форм (ОКНФ). Получены свойства ОКНФ для m-юнктивных предикатов. Показано, что каждый m-юнктивный предикат может быть представлен полностью согласованной ОКНФ, в которой каждый конъюнкт содержит не более m переменных. Такое представление m-юнктивного предиката названо приведённым. Предложен быстрый алгоритм нахождения приведённого представления m-юнктивного предиката. Показано, как полученные свойства ОКНФ для m-юнктивных предикатов можно применить для построения быстрого алгоритма задачи обобщённой S-выполнимости, в которой множество S содержит только предикаты, инвариантные относительно одной и той же функции почти единогласия.
- Добавил в систему: Селезнева Светлана Николаевна
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | selezneva-daor-19.pdf | 299,6 КБ | 10 сентября 2019 [selezn@cs.msu.su] |