RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Ереванского государственного университета, серия Физические и Математические науки // Архив

Уч. записки ЕГУ, сер. Физика и Математика, 2010, выпуск 1, страницы 61–63 (Mi uzeru206)

Эта публикация цитируется в 1 статье

Communications
Mathematics

On the Rabin’s speed-up of proofs for some systems of first order logic

[Об ускорении Рабина для выводов в некоторых системах логики первого порядка]

A. A. Chubaryan, H. R. Bolibekyan

Chair of Discrete Mathematics and Theoretical Computer Science YSU, Armenia

Аннотация: В статье рассматривается понятие стандартной теории. Для ряда систем исчисления предикатов первого порядка доказано, что они являются стандартными. На основе понятия стандартной теории проведен анализ сложности выводов в указанных системах.

Ключевые слова: speed-up, proof complexity, predicate calculus, ordinary theory.

Поступила в редакцию: 16.10.2009
Принята в печать: 16.12.2009

Язык публикации: английский



© МИАН, 2024