Speed-up for propositional Frege systems via generalizations of proofs

Jan Krajíček

Commentationes Mathematicae Universitatis Carolinae (1989)

  • Volume: 030, Issue: 1, page 137-140
  • ISSN: 0010-2628

How to cite

top

Krajíček, Jan. "Speed-up for propositional Frege systems via generalizations of proofs." Commentationes Mathematicae Universitatis Carolinae 030.1 (1989): 137-140. <http://eudml.org/doc/17708>.

@article{Krajíček1989,
author = {Krajíček, Jan},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Frege system; speed-up},
language = {eng},
number = {1},
pages = {137-140},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Speed-up for propositional Frege systems via generalizations of proofs},
url = {http://eudml.org/doc/17708},
volume = {030},
year = {1989},
}

TY - JOUR
AU - Krajíček, Jan
TI - Speed-up for propositional Frege systems via generalizations of proofs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1989
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 030
IS - 1
SP - 137
EP - 140
LA - eng
KW - Frege system; speed-up
UR - http://eudml.org/doc/17708
ER -

References

top
  1. G. C. Cejtin A. A. Čubarjan, On some bounds to the lengths of logical proofs in classical propositional calculus, (Russian), Truudy Vyčisl. Centra AN ArmSSR i Erevan. univ. 8 (1975), 57-64. (1975) MR0469688
  2. S. A. Cook R. A. Reckhow, The relative efficiency of propositional proof systems, J. Symb. Logic 44 (1979), 36-50. (1979) Zbl0408.03044MR0523487
  3. M. Dowd, Model-theoretic aspects of P N P , preprint (1985). (1985) 
  4. W. F. Farmer, Length of proofs and unification theory, Ph.D. thesis, Univ. of Wisconsin-Madison, 1984. (1984) 
  5. J. Krajíček, On the number of steps in proofs, to appear in Annals of Pure and Applied Logic. Zbl0672.03042MR0983000
  6. J. Krajíček P. Pudlák, The number of proof lines and the size of proofs in first order logic, Archive for Mathematical Logic 27 (1988), 69-84. (1988) Zbl0644.03032MR0955313
  7. J. Krajíček P. Pudlák, Propositional proof systems, the consistency of first order theories and the complexity of computations, to appear in J. Symbolic Logic. Zbl0696.03029MR1011192
  8. R. Parikh, Some results on the length of proofs, Trans. Amer. Math. Soc. 117 (1973), 29-36. (1973) Zbl0269.02011MR0432416

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.