A characterization of alternating log time by ramified recurrence

DOI10.1016/S0304-3975(99)00209-1MaRDI QIDQ1978645zbMATH OpenFDO

Authors 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

implicit computational complexityalternationramified recursionalogtimerecursion with substitution parameterstree recursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cites work

• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 176211 (Why is no real title available?)
• scientific article; zbMATH DE number 1339873 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 3444792 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• scientific article; zbMATH DE number 3291106 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Alternation
• An algebra and a logic for \(NC^ 1\)
• Function-algebraic characterizations of log and polylog parallel time
• On uniform circuit complexity
• The realm of primitive recursion

Cited in

(10)

• The equivalence of theories that characterize ALogTime
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• A Characterization of Alternating Log Time by First Order Functional Programs
• 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
• scientific article; zbMATH DE number 7559295 (Why is no real title available?)
• 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)