Streams and strings in formal proofs.

DOI10.1016/S0304-3975(01)00145-1MaRDI QIDQ1853510zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yanyan Li

Publication date 21 January 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(01)00145-1

zbMATH Keywords

Proof complexityDirected graphsCut eliminationCycles in proofsDuplicationLogical flow graphsStructure of proofs

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Grammars and rewriting systems (68Q42) Structure of proofs (03F07) Complexity of proofs (03F20)

Recommendations

• Proofs without syntax
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Streams are forever
• scientific article; zbMATH DE number 7204450
• Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination

Cites work

• scientific article; zbMATH DE number 4033738 (Why is no real title available?)
• scientific article; zbMATH DE number 1493054 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• Asymptotic cyclic expansion and bridge groups of formal proofs
• Bounds for proof-search and speed-up in the predicate calculus
• Cycling in proofs and feasibility
• Duplication of directed graphs and exponential blow up of proofs
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Linear logic
• Looking from the inside and from the outside
• Lower Bounds on Herbrand's Theorem
• Lower bounds for increasing complexity of derivations after cut elimination
• Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination
• Proof theory. 2nd ed
• The intractability of resolution
• The undecidability of k-provability
• Turning cycles into spirals
• Untersuchungen über das logische Schliessen. I

Cited in

(6)

• Logical structures and genus of proofs
• scientific article; zbMATH DE number 177653 (Why is no real title available?)
• scientific article; zbMATH DE number 1481753 (Why is no real title available?)
• Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination
• Group cancellation and resolution
• Interpolants, cut elimination and flow graphs for the propositional calculus

This page was built for publication: Streams and strings in formal proofs.

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