LOGSPACE and PTIME characterized by programming languages

DOI10.1016/S0304-3975(98)00357-0zbMath0954.68075OpenAlexW2027321599MaRDI QIDQ1575880

Neil D. Jones

Publication date: 23 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00357-0

zbMATH Keywords

PTIMELOGSPACE

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (19)

Computation by interaction for space-bounded functional programming ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Regressive computations characterize logarithmic space ⋮ Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\) ⋮ Unnamed Item ⋮ A Characterisation of the Relations Definable in Presburger Arithmetic ⋮ Subclasses of \textsc{Ptime} interpreted by programming languages ⋮ Read/write factorizable programs ⋮ Pure Iteration and Periodicity ⋮ Recursion in Higher Types and Resource Bounded Turing Machines ⋮ Unnamed Item ⋮ A Refinement of the μ-measure for Stack Programs ⋮ Quasi-interpretations. A way to control resources ⋮ Ramified Corecurrence and Logspace ⋮ Bounded minimalisation and bounded counting in argument-bounded idc's ⋮ Unbounded recursion and non-size-increasing functions ⋮ Complexity classes and fragments of C ⋮ An abstract approach to stratification in linear logic ⋮ A higher-order characterization of probabilistic polynomial time

This page was built for publication: LOGSPACE and PTIME characterized by programming languages