Regressive computations characterize logarithmic space

DOI10.1016/J.IC.2016.07.002MaRDI QIDQ342702zbMATH OpenOpenAlexFDO

Authors S. 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)

Recommendations

• On logarithmic-space computable real numbers
• Logarithmically convergent relaxation computation
• L-recursion and a new logic for logarithmic space
• L-recursion and a new logic for logarithmic space
• Approximation in (poly-) logarithmic space
• Approximation in (Poly-) Logarithmic Space
• Unambiguous functions in logarithmic space
• scientific article; zbMATH DE number 1072535
• scientific article; zbMATH DE number 5245122
• scientific article; zbMATH DE number 4108927

Cites work

• scientific article; zbMATH DE number 806747 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• A machine description and the hierarchy of initial Grzegorczyk classes
• Applicative theories for logarithmic complexity classes
• LOGSPACE and PTIME characterized by programming languages
• Logspace without bounds
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• Predecessor machines
• Programming Languages and Systems
• Unbounded recursion and non-size-increasing functions

Cited in

(2)

• Logical Approaches to Computational Barriers
• Unbounded recursion and non-size-increasing functions

This page was built for publication: Regressive computations characterize logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342702)