Sufficient conditions for cut elimination with complexity analysis

DOI10.1016/j.apal.2007.08.001zbMath1145.03033OpenAlexW2087025946MaRDI QIDQ2461191

João Rasga

Publication date: 27 November 2007

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2007.08.001

zbMATH Keywords

sequent calculuscomplexity of cut elimination

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05)

Related Items

Cut-elimination for quantified conditional logic, Interpolation via translations, Cut elimination in coalgebraic logics, Cut Elimination for Shallow Modal Logics

Uses Software

• Pesca

Cites Work

• Linear logic
• The unprovability of small inconsistency. A study of local and global interpretability
• Towards a semantic characterization of cut-elimination
• Duplication of directed graphs and exponential blow up of proofs
• Cut elimination and automatic proof procedures
• Bounds for cut elimination in intuitionistic propositional logic
• Intuitionistic propositional logic is polynomial-space complete
• Cut normal forms and proof complexity
• Depth of proofs, depth of cut-formulas and complexity of cut formulas
• Indexed systems of sequents and cut-elimination
• Display logic
• The role of quantifier alternations in cut elimination
• Non-deterministic Multiple-valued Structures
• The Mathematics of Sentence Structure
• Contraction-free sequent calculi for intuitionistic logic
• The relative efficiency of propositional proof systems
• Which structural rules admit cut elimination? An algebraic criterion
• Modal Sequent Calculi Labelled with Truth Values: Cut Elimination
• Cut-elimination and redundancy-elimination by resolution
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item