A characterization of alternating log time by ramified recurrence

DOI10.1016/S0304-3975(99)00209-1zbMath0943.68080MaRDI QIDQ1978645

D. D. Leivant, J.-Y. J.-Y. Marion

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

alternationimplicit computational complexityramified recursionalogtimerecursion with substitution parameterstree recursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ Algorithmically broad languages for polynomial time and space ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Recursion Schemata for NC k ⋮ Unnamed Item ⋮ Taming Modal Impredicativity: Superlazy Reduction ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity

Cites Work

• The realm of primitive recursion
• On uniform circuit complexity
• A new recursion-theoretic characterization of the polytime functions
• Function-algebraic characterizations of log and polylog parallel time
• An algebra and a logic for \(NC^ 1\)
• Alternation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of alternating log time by ramified recurrence