Axiomatizing proof tree concepts in bounded arithmetic

DOI10.4230/LIPICS.CSL.2012.440MaRDI QIDQ4649564zbMATH OpenFDO

Authors Satoru Kuroda

Publication date 22 November 2012

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2012.440

zbMATH Keywords

bounded arithmeticLOGCFLLOGDCFLproof tree

Mathematics Subject Classification ID

Structure of proofs (03F07) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Generalized quantifier and a bounded arithmetic theory for LOGCFL
• Bounded arithmetic for NC, ALogTIME, L and NL
• Logical foundations of proof complexity
• On theories of bounded arithmetic for \(\mathrm{NC}^1\)
• Independence results about context-free languages and lower bounds

Cited in

(8)

• Independence results about context-free languages and lower bounds
• From cut-free calculi to automated deduction: the case of bounded contraction
• A complete axiomatization of a theory with feature and arity constraints
• scientific article; zbMATH DE number 5722772 (Why is no real title available?)
• scientific article; zbMATH DE number 2196511 (Why is no real title available?)
• Axiomatising tree-interpretable structures
• The bounded proof property via step algebras and step frames
• Generalized quantifier and a bounded arithmetic theory for LOGCFL

This page was built for publication: Axiomatizing proof tree concepts in bounded arithmetic

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