Axiomatizing proof tree concepts in bounded arithmetic

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

Authors: Satoru Kuroda 

Publication date: 22 November 2012

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

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)

Cited In (8)

• Independence results about context-free languages and lower bounds
• Axiomatising tree-interpretable structures
• From cut-free calculi to automated deduction: the case of bounded contraction
• Title not available (Why is that?)
• Generalized quantifier and a bounded arithmetic theory for LOGCFL
• A complete axiomatization of a theory with feature and arity constraints
• The bounded proof property via step algebras and step frames
• Title not available (Why is that?)

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)