Bounded arithmetic and descriptive complexity

DOI10.1007/3-540-44622-2_15MaRDI QIDQ2753676zbMATH OpenFDO

Authors Achim Blumensath

Publication date 11 November 2001

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

Full work available at URL https://doi.org/10.1007/3-540-44622-2_15

zbMATH Keywords

arithmeticdefinabilitydescriptive complexity

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Descriptive complexity and finite models (68Q19)

Recommendations

• Arithmetical definability and computational complexity
• Bounded arithmetic for NC, ALogTIME, L and NL
• scientific article; zbMATH DE number 1978903
• Computer Science Logic
• The descriptive complexity of the fixed-points of bounded formulas

Cited in

(13)

• Bounded arithmetic for NC, ALogTIME, L and NL
• Bounded arithmetic, proof complexity and two papers of Parikh
• Arithmetical definability and computational complexity
• Relating the bounded arithmetic and polynomial time hierarchies
• The descriptive complexity of the fixed-points of bounded formulas
• Bounded minimalisation and bounded counting in argument-bounded idc's
• scientific article; zbMATH DE number 1263207 (Why is no real title available?)
• scientific article; zbMATH DE number 3995646 (Why is no real title available?)
• Characterizations of interpretability in bounded arithmetic
• Computer Science Logic
• Third-Order Computation and Bounded Arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Bounded fixed-point definability and tabular recognition of languages

This page was built for publication: Bounded arithmetic and descriptive complexity

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