Linear ramified higher type recursion and parallel complexity

DOI10.1007/3-540-45504-3_1MaRDI QIDQ4436023zbMATH OpenFDO

Authors Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg, Sebastiaan A. Terwijn

Publication date 23 November 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2183/21830001.htm

zbMATH Keywords

higher typesimplicit computational complexitylambda calculuslinear logicNCparallel computationrecursion

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Higher-type and set recursion theory (03D65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Higher type recursion, ramification and polynomial time
• On the expressivity of linear recursion schemes
• Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity
• Types for complexity of parallel computation in pi-calculus
• Recursion in Higher Types and Resource Bounded Turing Machines
• Linear types and non-size-increasing polynomial time computation.
• scientific article; zbMATH DE number 3954267
• Linear complexity parallel algorithms for linear systems of equations with recursive structure
• On the parallel complexity of solving recurrence equations
• Compilation and evaluation of linear mutual recursions

Cited in

(5)

• Implicit characterizations of FPTIME and NC revisited
• Higher type recursion, ramification and polynomial time
• The geometry of linear higher-order recursion
• Types for Proofs and Programs
• Characterizing parallel time by type 2 recursions with polynomial output length

This page was built for publication: Linear ramified higher type recursion and parallel complexity

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