Recursion Schemata for NC k

DOI10.1007/978-3-540-87531-4_6zbMath1157.03019OpenAlexW2155605358MaRDI QIDQ3540170

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

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

On sharing, memoization, and polynomial time ⋮ Upper Bounds on Stream I/O Using Semantic Interpretations ⋮ A higher-order characterization of probabilistic polynomial time

Cites Work

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

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