A characterization of alternating log time by ramified recurrence

DOI10.1016/S0304-3975(99)00209-1zbMATH Open0943.68080MaRDI QIDQ1978645FDOQ1978645

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

Publication date: 4 June 2000

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

Recommendations

• A Characterization of Alternating Log Time by First Order Functional Programs
• scientific article; zbMATH DE number 806752
• Publication:4725752
• On log-time alternating Turing machines of alternation depth k
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• scientific article; zbMATH DE number 2079048
• Function-algebraic characterizations of log and polylog parallel time
• Sequence complexity, rigidity and logarithmic Sarnak conjecture
• Log-concavity of \(P\)-recursive sequences
• Asymptotic \(r\)-log-convexity and P-recursive sequences

zbMATH Keywords

implicit computational complexityalternationramified recursionalogtimerecursion with substitution parameterstree recursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (10)

• The equivalence of theories that characterize ALogTime
• A Characterization of Alternating Log Time by First Order Functional Programs
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• A Characterization of NC k by First Order Functional Programs
• Algorithmically broad languages for polynomial time and space
• Invariance properties of RAMs and linear time
• Taming Modal Impredicativity: Superlazy Reduction
• Title not available (Why is that?)
• Recursion Schemata for NC k

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

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