On the proof complexity of cut-free bounded deep inference

DOI10.1007/978-3-642-22119-4_12MaRDI QIDQ3010365zbMATH OpenOpenAlexFDO

Authors Anupam Das

Publication date 1 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22119-4_12

Mathematics Subject Classification ID

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

Recommendations

• On the proof complexity of deep inference
• Interaction and depth against nondeterminism in proof search
• Complexity of Deep Inference via Atomic Flows
• Extension without cut
• Deep Proof Search in MELL

Cites work

• A proof calculus which reduces syntactic bureaucracy
• Deep inference and symmetry in classical proofs
• Extension without cut
• scientific article; zbMATH DE number 949290 (Why is no real title available?)
• scientific article; zbMATH DE number 953683 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Normalisation Control in Deep Inference via Atomic Flows
• On the proof complexity of deep inference
• Quasipolynomial Normalisation in Deep Inference via Atomic Flows and Threshold Formulae
• The relative efficiency of propositional proof systems

Cited in

(9)

• Complexity of Deep Inference via Atomic Flows
• On the proof complexity of deep inference
• On linear rewriting systems for Boolean logic and some applications to proof theory
• A Quasipolynomial Cut-Elimination Procedure in Deep Inference via Atomic Flows and Threshold Formulae
• A first order system with finite choice of premises
• Proof Complexity of the Cut-free Calculus of Structures
• A Subatomic Proof System for Decision Trees
• Interaction and depth against nondeterminism in proof search
• Extension without cut

This page was built for publication: On the proof complexity of cut-free bounded deep inference

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