Axiomatizing proof tree concepts in bounded arithmetic

DOI10.4230/LIPICS.CSL.2012.440zbMATH Open1252.03129MaRDI QIDQ4649564FDOQ4649564

Authors Satoru Kuroda

Publication date 22 November 2012

zbMATH Keywords

bounded arithmeticproof treeLOGCFLLOGDCFL

Mathematics Subject Classification ID

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

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

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)