Abstract.
We characterize complexity classes by function algebras that neither contain bounds nor any kind of variable segregation. The class of languages decidable in logarithmic space is characterized by the closure of a neat class of initial functions (projections and constants) under composition and simultaneous recursion on notation. We give a similar characterization of the class of number-theoretic 0–1 valued functions computable in linear space using simultaneous recursion on natural numbers in place of simultaneous recursion on notation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Manuscript received 1 September 2002
Rights and permissions
About this article
Cite this article
Kristiansen, L. Neat function algebraic characterizations of logspace and linspace. comput. complex. 14, 72–88 (2005). https://doi.org/10.1007/s00037-005-0191-0
Issue Date:
DOI: https://doi.org/10.1007/s00037-005-0191-0