From normal functors to logarithmic space queries
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...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2019
|
| _version_ | 1797077887129485312 |
|---|---|
| author | Nguyên, L Pradic, P |
| author_facet | Nguyên, L Pradic, P |
| author_sort | Nguyên, L |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:24:28Z |
| format | Conference item |
| id | oxford-uuid:7da85208-2bf1-4f0e-81cc-2835094d18f8 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:24:28Z |
| publishDate | 2019 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:7da85208-2bf1-4f0e-81cc-2835094d18f82022-03-26T21:05:04ZFrom normal functors to logarithmic space queriesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:7da85208-2bf1-4f0e-81cc-2835094d18f8Symplectic Elements at OxfordSchloss Dagstuhl2019Nguyên, LPradic, PWe 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. |
| spellingShingle | Nguyên, L Pradic, P From normal functors to logarithmic space queries |
| title | From normal functors to logarithmic space queries |
| title_full | From normal functors to logarithmic space queries |
| title_fullStr | From normal functors to logarithmic space queries |
| title_full_unstemmed | From normal functors to logarithmic space queries |
| title_short | From normal functors to logarithmic space queries |
| title_sort | from normal functors to logarithmic space queries |
| work_keys_str_mv | AT nguyenl fromnormalfunctorstologarithmicspacequeries AT pradicp fromnormalfunctorstologarithmicspacequeries |