Recursion Schemata for NC k

DOI10.1007/978-3-540-87531-4_6MaRDI QIDQ3540170zbMATH OpenOpenAlexFDO

Authors Guillaume Bonfante, Reinhard Kahle, Jean-Yves Marion, Isabel Oitavem

Publication date 20 November 2008

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-87531-4_6

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Towards an Implicit Characterization of NC k
• An algebra and a logic for \(NC^ 1\)
• scientific article; zbMATH DE number 176199
• Recursion schemata for slowly growing depth circuit classes
• Implicit characterizations of FPTIME and NC revisited

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• A Characterization of Alternating Log Time by First Order Functional Programs
• A characterization of alternating log time by ramified recurrence
• A new recursion-theoretic characterization of the polytime functions
• A program logic for resources
• Alternation
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Characterizing NC with tier 0 pointers
• Light linear logic
• New Computational Paradigms
• On uniform circuit complexity
• Predicative Analysis of Feasibility and Diagonalization
• Separating NC along the \(\delta\) axis
• The realm of primitive recursion
• Towards an Implicit Characterization of NC k

Cited in

(10)

• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• scientific article; zbMATH DE number 176199 (Why is no real title available?)
• scientific article; zbMATH DE number 3995649 (Why is no real title available?)
• Towards an Implicit Characterization of NC k
• A Characterization of NC k by First Order Functional Programs
• Recursion schemata for slowly growing depth circuit classes
• Characterizing NC with tier 0 pointers
• Upper Bounds on Stream I/O Using Semantic Interpretations
• A higher-order characterization of probabilistic polynomial time
• On sharing, memoization, and polynomial time

This page was built for publication: Recursion Schemata for NC k

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