License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.123
URN: urn:nbn:de:0030-drops-106994
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10699/
Nguyen, Lê Thành Dung ;
Pradic, Pierre
From Normal Functors to Logarithmic Space Queries
Abstract
We introduce a new approach to implicit complexity in linear logic, inspired by functional database query languages and using recent developments in effective denotational semantics of polymorphism. We give the first sub-polynomial upper bound in a type system with impredicative polymorphism; adding restrictions on quantifiers yields a characterization of logarithmic space, for which extensional completeness is established via descriptive complexity.
BibTeX - Entry
@InProceedings{nguyen_et_al:LIPIcs:2019:10699,
author = {Lê Th{\`a}nh Dung Nguyen and Pierre Pradic},
title = {{From Normal Functors to Logarithmic Space Queries}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {123:1--123:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10699},
URN = {urn:nbn:de:0030-drops-106994},
doi = {10.4230/LIPIcs.ICALP.2019.123},
annote = {Keywords: coherence spaces, elementary linear logic, semantic evaluation}
}
|
Keywords: |
|
coherence spaces, elementary linear logic, semantic evaluation |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
