Implicit characterizations of FPTIME and NC revisited
From MaRDI portal
Publication:1044672
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
function algebra; implicit computational complexity; NC; polynomial-time computability; bounded and ramified forms of recursion
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, Subclasses of \textsc{Ptime} interpreted by programming languages, Algorithmically broad languages for polynomial time and space
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item