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)

Full work available at URL https://doi.org/10.1016/S0304-3975(99)00209-1

zbMATH Keywords

alogtimealternationimplicit computational complexityramified recursionrecursion 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

• 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
• 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?)
• On uniform circuit complexity
• The realm of primitive recursion

Cited in

(11)

• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Invariance properties of RAMs and linear time
• Algorithmically broad languages for polynomial time and space
• Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits
• A Characterization of NC k by First Order Functional Programs
• Recursion Schemata for NC k
• Taming Modal Impredicativity: Superlazy Reduction
• Pointers in recursion: exploring the tropics
• A Characterization of Alternating Log Time by First Order Functional Programs
• Towards new characterizations of small circuit classes via discrete ordinary differential equations
• The equivalence of theories that characterize ALogTime

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)