Cycling in proofs and feasibility

DOI10.1090/S0002-9947-99-02300-4zbMath0941.03064MaRDI QIDQ4942870

No author found.

Publication date: 15 March 2000

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

cut eliminationcycles in proofsdynamics of proofsfeasible numberscycles in logical graphsfeasibility of large numberslogical flow graphs of proofslower bound for concrete consistency

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Structure of proofs (03F07) Complexity of proofs (03F20)

Related Items (7)

The cost of a cycle is a square ⋮ Radical anti-realism, Wittgenstein and the length of proofs ⋮ Asymptotic cyclic expansion and bridge groups of formal proofs ⋮ On the form of witness terms ⋮ Turning cycles into spirals ⋮ Bounded arithmetic, proof complexity and two papers of Parikh ⋮ Streams and strings in formal proofs.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Don't eliminate cut
• Lower bounds for increasing complexity of derivations after cut elimination
• The undecidability of \(k\)-provability
• Turning cycles into spirals
• Looking from the inside and from the outside
• Bounds for proof-search and speed-up in the predicate calculus
• Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination
• Existence and feasibility in arithmetic

This page was built for publication: Cycling in proofs and feasibility