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

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

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



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискретн. анализ и исслед. опер., 2019, том 26, номер 3, страницы 46–59 (Mi da930)  

Об $m$-юнктивных предикатах на конечном множестве

С. Н. Селезнева

Московский гос. университет им. М. В. Ломоноcова, Ленинские горы, 1, 119991 Москва, Россия

Аннотация: Рассматриваются предикаты на конечных множествах. Предикаты, инвариантные относительно некоторой $(m+1)$-местной функции почти единогласия, названы $m$-юнктивными. Предлагается представление предикатов на конечном множестве в виде обобщённых конъюнктивных нормальных форм (ОКНФ). Получены свойства ОКНФ для $m$-юнктивных предикатов. Показано, что каждый $m$-юнктивный предикат может быть представлен полностью согласованной ОКНФ, в которой каждый конъюнкт содержит не более $m$ переменных. Такое представление $m$-юнктивного предиката названо приведённым. Предложен быстрый алгоритм нахождения приведённого представления $m$-юнктивного предиката. Показано, как полученные свойства ОКНФ для $m$-юнктивных предикатов можно применить для построения быстрого алгоритма задачи обобщённой $S$-выполнимости, в которой множество $S$ содержит только предикаты, инвариантные относительно одной и той же функции почти единогласия. Библиогр. 15.

Ключевые слова: предикат на конечном множестве, функция на конечном множестве, функция почти единогласия, биюнктивный предикат, $m$-юнктивный предикат, конъюнктивная нормальная форма, задача обобщённой выполнимости.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17–01–00782_a
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 17–01–00782-а).


DOI: https://doi.org/10.33048/daio.2019.26.647

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2019, 13:3, 528–535

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

Тип публикации: Статья
УДК: 519.7
Статья поступила: 05.02.2019
Переработанный вариант: 21.03.2019
Принята к публикации: 25.03.2019

Образец цитирования: С. Н. Селезнева, “Об $m$-юнктивных предикатах на конечном множестве”, Дискретн. анализ и исслед. опер., 26:3 (2019), 46–59; J. Appl. Industr. Math., 13:3 (2019), 528–535

Цитирование в формате AMSBIB
\RBibitem{Sel19}
\by С.~Н.~Селезнева
\paper Об $m$-юнктивных предикатах на~конечном~множестве
\jour Дискретн. анализ и исслед. опер.
\yr 2019
\vol 26
\issue 3
\pages 46--59
\mathnet{http://mi.mathnet.ru/da930}
\crossref{https://doi.org/10.33048/daio.2019.26.647}
\transl
\jour J. Appl. Industr. Math.
\yr 2019
\vol 13
\issue 3
\pages 528--535
\crossref{https://doi.org/10.1134/S199047891903013X}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85071382746}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da930
  • http://mi.mathnet.ru/rus/da/v26/i3/p46

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:20
    Литература:2
    Первая стр.:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019