Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
2014Available
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:
  • Organisation
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us