Implicit characterizations of FPTIME and NC revisited

DOI10.1016/j.jlap.2009.02.005zbMath1192.68299MaRDI QIDQ1044672

Henning Wunderlich, Karl-Heinz Niggl

Publication date: 18 December 2009

Published in: The Journal of Logic and Algebraic Programming (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:bsz:289-vts-64873

zbMATH Keywords

function algebra; implicit computational complexity; NC; polynomial-time computability; bounded and ramified forms of recursion

Mathematics Subject Classification ID

68Q60: Specification and verification (program logics, model checking, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Iteration on notation and unary functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The realm of primitive recursion
• A new recursion-theoretic characterization of the polytime functions
• Function-algebraic characterizations of log and polylog parallel time
• Linear types and non-size-increasing polynomial time computation.
• Higher type recursion, ramification and polynomial time
• The \(\mu\)-measure as a tool for classifying computational complexity
• Control structures in programs and computational complexity
• On the computational complexity of imperative programming languages
• Towards an Implicit Characterization of NC k
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs