The Library
Non-elementary complexities for branching VASS, MELL, and extensions
Tools
Tools
Tools
Lazic, Ranko and Schmitz, Sylvain (2014) Non-elementary complexities for branching VASS, MELL, and extensions. In: Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th ACM/IEEE Symposium on Logic in Computer Science, Vienna, Austria, 14-18 Jul 2014. Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Article number 61). ISBN 9781450328869. doi:10.1145/2603088.2603129
|
PDF
WRAP_Lazic_paper 120 %281%29.pdf - Accepted Version - Requires a PDF viewer. Download (979Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2603088.2603129
Abstract
We study the complexity of reachability problems on branching extensions of vector addition systems, which allows us to derive new non-elementary complexity bounds for fragments and variants of propositional linear logic. We show that provability in the multiplicative exponential fragment is non-elementary already in the affine case, and match this lower bound for the full propositional affine linear logic, proving its Tower-completeness. We also show that provability in propositional contractive linear logic is Ackermann-complete.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Logic, Symbolic and mathematical | ||||
| Journal or Publication Title: | Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||
| ISBN: | 9781450328869 | ||||
| Official Date: | 2014 | ||||
| Dates: |
|
||||
| Number: | Article number 61 | ||||
| DOI: | 10.1145/2603088.2603129 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Date of first compliant deposit: | 27 December 2015 | ||||
| Date of first compliant Open Access: | 27 December 2015 | ||||
| Funder: | France. Agence nationale de la recherche (ANR) | ||||
| Grant number: | ReacHard 11-BS02-001-01 (ANR) | ||||
| Embodied As: | 1 | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th ACM/IEEE Symposium on Logic in Computer Science | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Vienna, Austria | ||||
| Date(s) of Event: | 14-18 Jul 2014 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
