Generalized quantifier and a bounded arithmetic theory for LOGCFL

DOI10.1007/S00153-007-0052-4MaRDI QIDQ884960zbMATH OpenOpenAlexFDO

Authors Satoru Kuroda

Publication date 7 June 2007

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-007-0052-4

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Axiomatizing proof tree concepts in bounded arithmetic
• The descriptive complexity approach to LOGCFL
• Bounded arithmetic for NC, ALogTIME, L and NL
• scientific article; zbMATH DE number 1304331
• Properties that characterize LOGCFL

Cites work

• Computer Science Logic
• Extensions to Barrington's M-program model
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 2196512 (Why is no real title available?)
• Notes on polynomially bounded arithmetic
• Properties that characterize LOGCFL
• The descriptive complexity approach to LOGCFL
• Theories for TC0 and Other Small Complexity Classes
• Two Applications of Inductive Counting for Complementation Problems

Cited in

(6)

• Structure and definability in general bounded arithmetic theories
• Properties that characterize LOGCFL
• Canonical Gentzen-Type Calculi with (n,k)-ary Quantifiers
• scientific article; zbMATH DE number 1304331 (Why is no real title available?)
• Axiomatizing proof tree concepts in bounded arithmetic
• The descriptive complexity approach to LOGCFL

This page was built for publication: Generalized quantifier and a bounded arithmetic theory for LOGCFL

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