О сложности проблемы эквивалентности хорновским формулам. II Научная публикация
| Журнал |
Алгебра и логика
ISSN: 0373-9252 |
||
|---|---|---|---|
| Вых. Данные | Год: 2022, Том: 61, Номер: 4, Страницы: 469-482 Страниц : 14 DOI: 10.33048/alglog.2022.61.406 | ||
| Ключевые слова | хорновская формула, m-сводимость, Σ01-множество | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0011 |
| 2 | Российский фонд фундаментальных исследований | 20-01-00300 |
Реферат:
Изучается сложность проблемы существования хорновского предложения, эквивалентного данному предложению. Доказывается, что для сигнатуры, состоящей из одного одноместного функционального символа и любого конечного числа одноместных предикатных символов, данная проблема вычислима. Если же сигнатура содержит хотя бы два одноместных функциональных символа, устанавливается, что указанная проблема является m-полным Σ01-множеством.
Библиографическая ссылка:
Когабаев Н.Т.
О сложности проблемы эквивалентности хорновским формулам. II
Алгебра и логика. 2022. Т.61. №4. С.469-482. DOI: 10.33048/alglog.2022.61.406 РИНЦ
О сложности проблемы эквивалентности хорновским формулам. II
Алгебра и логика. 2022. Т.61. №4. С.469-482. DOI: 10.33048/alglog.2022.61.406 РИНЦ
Переводная:
Kogabaev N.T.
Complexity of the problem of being equivalent to Horn formulas. II
Algebra and Logic. 2022. V.61. N4. P.318-327. DOI: 10.1007/s10469-023-09700-7 WOS Scopus РИНЦ OpenAlex
Complexity of the problem of being equivalent to Horn formulas. II
Algebra and Logic. 2022. V.61. N4. P.318-327. DOI: 10.1007/s10469-023-09700-7 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 16 февр. 2022 г. |
| Принята к публикации: | 29 мар. 2023 г. |
| Опубликована в печати: | 6 апр. 2023 г. |
| Опубликована online: | 6 апр. 2023 г. |
Идентификаторы БД:
| РИНЦ: | 50464757 |
Цитирование в БД:
| БД | Цитирований |
|---|---|
| РИНЦ | 1 |