An Implicit Characterization of PSPACE

DOI10.1145/2159531.2159540zbMath1351.68107arXiv1006.0030OpenAlexW2146459129MaRDI QIDQ2946666

Jean-Yves Marion, Marco Gaboardi, Simonetta Ronchi della Rocca

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.0030

zbMATH Keywords

operational semanticslinear logicimplicit computational complexitypolynomial spacetype assignment

Mathematics Subject Classification ID

Logic in computer science (03B70) Semantics in the theory of computing (68Q55) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatory logic and lambda calculus (03B40)

Related Items (4)

Computational Complexity Via Finite Types ⋮ Polynomial time in untyped elementary linear logic ⋮ Unary Resolution: Characterizing Ptime ⋮ Implicit computation complexity in higher-order programming languages

This page was built for publication: An Implicit Characterization of PSPACE