ON THE RABIN’S SPEED-UP OF PROOFS FOR SOME SYSTEMS OF FIRST ORDER LOGIC

A. A. Chubaryan; H. R. Bolibekyan

doi:10.46991/PYSU:A/2010.44.1.061

ON THE RABIN’S SPEED-UP OF PROOFS FOR SOME SYSTEMS OF FIRST ORDER LOGIC

Authors

A. A. Chubaryan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia
H. R. Bolibekyan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2010.44.1.061

Keywords:

speed-up, proof complexity, predicate calculus, ordinary theory

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.

Downloads

Published

2010-01-26

How to Cite

Chubaryan, A. A., & Bolibekyan, H. R. (2010). ON THE RABIN’S SPEED-UP OF PROOFS FOR SOME SYSTEMS OF FIRST ORDER LOGIC. Proceedings of the YSU A: Physical and Mathematical Sciences, 44(1 (221), 61–63. https://doi.org/10.46991/PYSU:A/2010.44.1.061