Complexity of the problem of being equivalent to Horn formulas. II Научная публикация
| Журнал |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||
|---|---|---|---|
| Вых. Данные | Год: 2022, Том: 61, Номер: 4, Страницы: 318-327 Страниц : 10 DOI: 10.1007/s10469-023-09700-7 | ||
| Ключевые слова | horn formula, m-reducibility, algebra, mathematical logic and foundations | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (2)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0011 |
| 2 | Российский фонд фундаментальных исследований | 20-01-00300 |
Реферат:
We look at the complexity of the existence problem for a Horn sentence equivalent to a given one. It is proved that for a signature consisting of one unary function symbol and any finite number of unary predicate symbols, the problem is computable. For a signature with at least two unary function symbols, it is stated that the problem mentioned is an m-complete ∑01set .
Библиографическая ссылка:
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
Оригинальная:
Когабаев Н.Т.
О сложности проблемы эквивалентности хорновским формулам. 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 РИНЦ
Даты:
| Поступила в редакцию: | 16 февр. 2022 г. |
| Опубликована online: | 30 сент. 2022 г. |
| Принята к публикации: | 29 мар. 2023 г. |
| Опубликована в печати: | 28 апр. 2023 г. |
Идентификаторы БД:
| Web of science: | WOS:000980226100001 |
| Scopus: | 2-s2.0-85153747027 |
| РИНЦ: | 59285581 |
| OpenAlex: | W4367314728 |