Nonelementary complexities for branching VASS, MELL, and extensions
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 6045
- Type
- D - Journal article
- DOI
-
10.1145/2733375
- Title of journal
- ACM Transactions on Computational Logic (TOCL)
- Article number
- Article number 20
- First page
- -
- Volume
- 16
- Issue
- 3
- ISSN
- 1529-3785
- Open access status
- Out of scope for open access requirements
- Month of publication
- May
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 8
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This well-cited article is the full version of a CSL-LICS'14 paper, the top international conference on logical aspects of computer science. The first to establish precise connections between linear logic and branching VASS, and to obtain optimal lower complexity bounds for both, this work has led to new query languages for XML databases (Abriola et al., FoSSaCS'17), progress in model checking functional programs (Cotton-Barratt et al., ACM ToPLaS 41(2)), and new algorithms for XPath (Baelde et al., PODS'19). Having been funded by ANR (11-BS02-001-01), this research has led to grants from EPSRC (EP/M011801/1), Leverhulme Trust (VP1-2014-041) and Royal Society (IE150122).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -