LOGSPACE and PTIME characterized by programming languages
From MaRDI portal
Publication:1575880
DOI10.1016/S0304-3975(98)00357-0zbMath0954.68075OpenAlexW2027321599MaRDI QIDQ1575880
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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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
