| Постоянная ссылка (СИД2) |
J2094749312X |
| Название |
АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ ТЕОРИЙ БИНАРНОГО ПРЕДИКАТА В ЯЗЫКАХ С МАЛЫМ ЧИСЛОМ ПЕРЕМЕННЫХ |
| Автор |
Рыбаков М. |
| Источник |
Доклады Российской академии наук. Математика, информатика, процессы управления |
| Страницы/Объём |
61-65 |
| Сокращ. назв. источника |
Докл. РАН. Мат., информатика, проц. упр. |
| Год |
2022 |
| Том |
507 |
| Адрес в Интернет |
http://elibrary.ru/item.asp?id=49991286 |
| Постоянная ссылка (СИД) |
J20947493 |
| Ключевые слова (авторские) |
диадическая логика%классическая логика предикатов%неразрешимость%теорема Трахтенброта%теорема |
| Место хранения |
Удаленный доступ. Эл. регистр. НЭБ |
| Дата регистрации в ВИНИТИ |
29.12.2022 |
| Язык текста |
русский |
| Аннотация |
Доказана σ10-трудность различных теорий бинарного предиката в языке с тремя предметными переменными и бинарной предикатной буквой (без констант и равенства). Показано, что при добавлении равенства, композиции и транзитивного замыкания получаются π11-трудные теории бинарного предиката при двух предметных переменных в языке |
| Тематический раздел |
Математика |