|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
МАТЕМАТИКА
Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных
М. Рыбаков Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Москва, Россия
Аннотация:
Доказана $\Sigma^0_1$-трудность различных теорий бинарного предиката в языке с тремя предметными переменными и бинарной предикатной буквой (без констант и равенства). Показано, что при добавлении равенства, композиции и транзитивного замыкания получаются $\Pi_1^1$-трудные теории бинарного предиката при двух предметных переменных в языке.
Ключевые слова:
классическая логика предикатов, диадическая логика, неразрешимость, теорема Чёрча, теорема Трахтенброта.
Образец цитирования:
М. Рыбаков, “Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных”, Докл. РАН. Матем., информ., проц. упр., 507 (2022), 61–65
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/danma320 https://www.mathnet.ru/rus/danma/v507/p61
|
Статистика просмотров: |
Страница аннотации: | 70 | Список литературы: | 22 |
|