A characterization of alternating log time by ramified recurrence
type: Item
instance of: scholarly article
title: A characterization of alternating log time by ramified recurrence
zbMATH Open document ID: 0943.68080
DOI: 10.1016/S0304-3975(99)00209-1
author: D. D. Leivant
author: J.-Y. J.-Y. Marion
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1454401
zbMATH Keywords: alogtime
zbMATH Keywords: alternation
zbMATH Keywords: ramified recursion
zbMATH Keywords: recursion with substitution parameters
zbMATH Keywords: tree recursion
zbMATH Keywords: implicit computational complexity
MaRDI profile type: Publication
cites work: A new recursion-theoretic characterization of the polytime functions
cites work: Function-algebraic characterizations of log and polylog parallel time
cites work: Alternation
cites work: Q4934292
cites work: Q4769966
cites work: An algebra and a logic for \(NC^ 1\)
cites work: Q5573940
cites work: Q4265595
cites work: Q4035315
cites work: Q4850553
cites work: Q4474861
cites work: Q3325707
cites work: On uniform circuit complexity
cites work: The realm of primitive recursion
Recommended article: A Characterization of Alternating Log Time by First Order Functional Programs
Recommended article: Q4850553
Recommended article: Q4725752
Recommended article: On log-time alternating Turing machines of alternation depth k
Recommended article: Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
Recommended article: Q4474861
Recommended article: Function-algebraic characterizations of log and polylog parallel time
Recommended article: Sequence complexity, rigidity and logarithmic Sarnak conjecture
Recommended article: Log-concavity of \(P\)-recursive sequences
Recommended article: Asymptotic \(r\)-log-convexity and P-recursive sequences
description: scientific article; zbMATH DE number 1454401