Unbounded recursion and non-size-increasing functions

DOI10.1016/j.entcs.2016.03.014zbMath1345.03077OpenAlexW2341184081WikidataQ113317690 ScholiaQ113317690MaRDI QIDQ737105

Stefano Mazzanti

Publication date: 5 August 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2016.03.014

zbMATH Keywords

logspace computable functionrecursion on notationpolynomial-time computable function

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (1)

Regressive computations characterize logarithmic space

Cites Work

• Unnamed Item
• Unnamed Item
• Regressive computations characterize logarithmic space
• The iterated mod problem
• Predecessor machines
• Linear types and non-size-increasing polynomial time computation.
• LOGSPACE and PTIME characterized by programming languages
• Neat function algebraic characterizations of LOGSPACE and LINSPACE

This page was built for publication: Unbounded recursion and non-size-increasing functions