Neat function algebraic characterizations of LOGSPACE and LINSPACE

DOI10.1007/S00037-005-0191-0zbMath1161.68477OpenAlexW2016299452MaRDI QIDQ1781116

Lars Kristiansen

Publication date: 16 June 2005

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-005-0191-0

zbMATH Keywords

Function algebrasLinspaceLogspaceRecursion schemes

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 (8)

Regressive computations characterize logarithmic space ⋮ A Characterisation of the Relations Definable in Presburger Arithmetic ⋮ Pure Iteration and Periodicity ⋮ Recursion in Higher Types and Resource Bounded Turing Machines ⋮ Ramified Corecurrence and Logspace ⋮ Bounded minimalisation and bounded counting in argument-bounded idc's ⋮ Unbounded recursion and non-size-increasing functions ⋮ Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)

This page was built for publication: Neat function algebraic characterizations of LOGSPACE and LINSPACE