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

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

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



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






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


Дискрет. матем., 1989, том 1, выпуск 2, страницы 65–77 (Mi dm910)  

О сложности решения задачи $\alpha$-выразимости в $k$-значной логике

Н. Р. Емельянов


Аннотация: В работе исследуется алгоритмическая сложность задачи распознавания принадлежности функции $k$-значной логики $\alpha$-замыканию системы функций. Понятие $\alpha$-замыкания возникает при исследованиях в теории конечных автоматов и является сужением понятия обычного замыкания. При $k=2$ показано существенное отличие решетки $\alpha$-замкнутых классов от известной решетки замкнутых классов. Это затрудняет построение эффективного алгоритма решения поставленной задачи без глубоких исследований решетки $\alpha$-замкнутых классов в $P_2$ При $k>2$ доказана NP-трудность поставленной задачи.

Полный текст: PDF файл (1547 kB)

Реферативные базы данных:
УДК: 519.716
Статья поступила: 05.10.1988

Образец цитирования: Н. Р. Емельянов, “О сложности решения задачи $\alpha$-выразимости в $k$-значной логике”, Дискрет. матем., 1:2 (1989), 65–77

Цитирование в формате AMSBIB
\RBibitem{Eme89}
\by Н.~Р.~Емельянов
\paper О~сложности решения задачи $\alpha$-выразимости в~$k$-значной логике
\jour Дискрет. матем.
\yr 1989
\vol 1
\issue 2
\pages 65--77
\mathnet{http://mi.mathnet.ru/dm910}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1035095}
\zmath{https://zbmath.org/?q=an:0733.03015}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm910
  • http://mi.mathnet.ru/rus/dm/v1/i2/p65

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