О сложности проблемы ∀-представимости предложений Научная публикация
| Журнал |
Алгебра и логика
ISSN: 0373-9252 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2023, Том: 62, Номер: 4, Страницы: 552-557 Страниц : 6 DOI: 10.33048/alglog.2023.62.406 | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (1)
| 1 | Российский научный фонд | 23-11-00170 |
Реферат:
Изучается сложность проблемы существования ∀-предложения (exists-предложения), эквивалентного данному предложению. Доказывается, что для сигнатуры, состоящей только из одноместных предикатных символов, обе данные проблемы вычислимы. Если же сигнатура содержит хотя бы два одноместных функциональных символа, установлено, что каждая из указанных проблем является m-полным Sigma^0_1-множеством.
Библиографическая ссылка:
Когабаев Н.Т.
О сложности проблемы ∀-представимости предложений
Алгебра и логика. 2023. Т.62. №4. С.552-557. DOI: 10.33048/alglog.2023.62.406 РИНЦ MathNet
О сложности проблемы ∀-представимости предложений
Алгебра и логика. 2023. Т.62. №4. С.552-557. DOI: 10.33048/alglog.2023.62.406 РИНЦ MathNet
Переводная:
Kogabaev N.T.
Complexity of the problem of ∀-representation for sentences
Algebra and Logic. 2023. V.62. N4. P.372-375. DOI: 10.1007/s10469-024-09751-4 WOS Scopus РИНЦ OpenAlex
Complexity of the problem of ∀-representation for sentences
Algebra and Logic. 2023. V.62. N4. P.372-375. DOI: 10.1007/s10469-024-09751-4 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 22 мар. 2024 г. |
| Опубликована в печати: | 27 апр. 2024 г. |
| Принята к публикации: | 19 июл. 2024 г. |
| Опубликована online: | 27 июл. 2024 г. |
Цитирование в БД:
Пока нет цитирований