The Library
Nonelementary complexities for branching VASS, MELL, and extensions.
Tools
Tools
Tools
Lazic, Ranko and Schmitz, Sylvain (2015) Nonelementary complexities for branching VASS, MELL, and extensions. ACM Transactions on Computational Logic (TOCL), Volume 16 (Number 3). Article number 20. doi:10.1145/2733375 ISSN 1529-3785.
|
PDF
WRAP_0070379-cs-070615-acm.pdf - Accepted Version - Requires a PDF viewer. Download (750Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2733375
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 Tower-hard already in the affine case—and hence non-elementary. We 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: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Computer science—Mathematics, Computational complexity, Computer logic | ||||
| Journal or Publication Title: | ACM Transactions on Computational Logic (TOCL) | ||||
| Publisher: | Association for Computing Machinery, Inc. | ||||
| ISSN: | 1529-3785 | ||||
| Official Date: | May 2015 | ||||
| Dates: |
|
||||
| Volume: | Volume 16 | ||||
| Number: | Number 3 | ||||
| Article Number: | Article number 20 | ||||
| DOI: | 10.1145/2733375 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Description: | Revised and extended version of an article presented at the Joint meeting of the 23rd EACSL Annual Conference on Computer Science Logic and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (CSL-LICS’14). |
||||
| Date of first compliant deposit: | 29 December 2015 | ||||
| Date of first compliant Open Access: | 29 December 2015 | ||||
| Funder: | France. Agence nationale de la recherche (ANR) | ||||
| Grant number: | 11-BS02-001-01 | ||||
| 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
