Regressive computations characterize logarithmic space

DOI10.1016/j.ic.2016.07.002zbMath1353.68087OpenAlexW2483796587MaRDI QIDQ342702

Stefano Mazzanti

Publication date: 18 November 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.07.002

zbMATH Keywords

logspace computable functionrecursion on notationregressive machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items

Unbounded recursion and non-size-increasing functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unbounded recursion and non-size-increasing functions
• A machine description and the hierarchy of initial Grzegorczyk classes
• Predecessor machines
• LOGSPACE and PTIME characterized by programming languages
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• Applicative theories for logarithmic complexity classes
• Programming Languages and Systems