Non-elementary speed-ups in logic calculi

DOI10.1002/MALQ.200710067zbMATH Open1163.03032OpenAlexW2166153399MaRDI QIDQ3545216FDOQ3545216

Toshiyasu Arai

Publication date: 10 December 2008

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200710067

Recommendations

• Non-elementary speed-ups in proof length by different variants of classical analytic calculi
• Polynomially and superexponentially shorter proofs in fragments of arithmetic
• Two recursion theoretic characterizations of proof speed-ups
• On the Rabin's speed-up of proofs for some systems of first order logic
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics

zbMATH Keywords

second-order logicspeed-upepsilon calculi

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Classical first-order logic (03B10) Complexity of proofs (03F20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The epsilon calculus and Herbrand complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower Bounds on Herbrand's Theorem
• Title not available (Why is that?)
• About the proof-theoretic ordinals of weak fixed point theories
• Eliminating definitions and Skolem functions in first-order logic
• The predicate calculus with \(\varepsilon\)-symbol
• Title not available (Why is that?)
• Title not available (Why is that?)
• Object logic and morphism logic
• Elimination Theorems of Uniqueness Conditions
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• Speedup for natural problems and noncomputability
• Intuitionistic fixed point theories over set theories

This page was built for publication: Non-elementary speed-ups in logic calculi

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545216)