@inproceedings{9e1639a55b9042f988ed9effe258bf12,
title = "Simple parsimonious types and logarithmic space",
abstract = "We present a functional characterization of deterministic logspace-computable predicates based on a variant (although not a subsystem) of propositional linear logic, which we call parsimonious logic. The resulting calculus is simply-typed and contains no primitive besides those provided by the underlying logical system, which makes it one of the simplest higher-order languages capturing logspace currently known. Completeness of the calculus uses the descriptive complexity characterization of logspace (we encode first-order logic with deterministic closure), whereas soundness is established by executing terms on a token machine (using the geometry of interaction).",
keywords = "Geometry of interaction, Implicit computational complexity, Linear logic",
author = "Damiano Mazza",
note = "Publisher Copyright: {\textcopyright} Damiano Mazza.; 24th EACSL Annual Conference on Computer Science Logic, CSL 2015 ; Conference date: 07-09-2015 Through 10-09-2015",
year = "2015",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.CSL.2015.24",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "24--40",
editor = "Stephan Kreutzer",
booktitle = "24th EACSL Annual Conference on Computer Science Logic, CSL 2015",
}