Non-elementary speed-ups in logic calculi

DOI10.1002/MALQ.200710067MaRDI QIDQ3545216zbMATH OpenOpenAlexFDO

Authors 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

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)

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

Cites work

• scientific article; zbMATH DE number 3140501 (Why is no real title available?)
• scientific article; zbMATH DE number 3849202 (Why is no real title available?)
• scientific article; zbMATH DE number 3668590 (Why is no real title available?)
• scientific article; zbMATH DE number 3765778 (Why is no real title available?)
• scientific article; zbMATH DE number 1215500 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1497485 (Why is no real title available?)
• scientific article; zbMATH DE number 3248792 (Why is no real title available?)
• About the proof-theoretic ordinals of weak fixed point theories
• Eliminating definitions and Skolem functions in first-order logic
• Elimination Theorems of Uniqueness Conditions
• Lower Bounds on Herbrand's Theorem
• Object logic and morphism logic
• The epsilon calculus and Herbrand complexity
• The predicate calculus with \(\varepsilon\)-symbol

Cited in

(6)

• Intuitionistic fixed point theories over set theories
• Rabin style speed-up of proofs. More generalized speed-up in the systems of first order logic
• Speedup for natural problems and noncomputability
• On the Rabin's speed-up of proofs for some systems of first order logic
• scientific article; zbMATH DE number 6698765 (Why is no real title available?)
• Non-elementary speed-ups in proof length by different variants of classical analytic calculi

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)