A. A. Chubaryan, H. R. Bolibekyan, “On the Rabin’s speed-up of proofs for some systems of first order logic”, Proceedings of the YSU, Physical and Mathematical Sciences, 2010, Issue 1,Pages <nobr>61

This article is cited in 1 paper

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

Abstract: In the paper a notion of ordinary theory is considered. It is proved that some systems of first order predicate calculus are ordinary. This property is used for a proof complexity comparison in the considered systems.

Keywords: speed-up, proof complexity, predicate calculus, ordinary theory.

Received: 16.10.2009
Accepted: 16.12.2009

Language: English