Implicit characterizations of FPTIME and NC revisited

DOI10.1016/j.jlap.2009.02.005zbMath1192.68299OpenAlexW2147387242MaRDI 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 algebraimplicit computational complexityNCpolynomial-time computabilitybounded and ramified forms of recursion

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Algorithmically broad languages for polynomial time and space ⋮ Subclasses of \textsc{Ptime} interpreted by programming languages ⋮ 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

This page was built for publication: Implicit characterizations of FPTIME and NC revisited