UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Context-free commutative grammars with integer counters and resets

Chistikov, D; Haase, C; Halfon, S; (2018) Context-free commutative grammars with integer counters and resets. Theoretical Computer Science , 735 pp. 147-161. 10.1016/j.tcs.2016.06.017. Green open access

[img]
Preview
Text
1511.04893(2).pdf - Accepted version

Download (317kB) | Preview

Abstract

We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on them. Those grammars can alternatively be viewed as an extension of communication-free Petri nets. Our main results are that reachability and coverability are inter-reducible and both NP-complete. In particular, this class of commutative grammars enjoys semi-linear reachability sets. We also show that the inclusion problem is, in general, coNEXP-complete and already Π2P-complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel Π2P-complete variant of the classic subset sum problem.

Type: Article
Title: Context-free commutative grammars with integer counters and resets
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.tcs.2016.06.017
Publisher version: https://doi.org/10.1016/j.tcs.2016.06.017
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Context-free commutative grammars, Communication-free Petri nets, Reset nets, Vector addition systems with states, Presburger arithmetic, Subset sum
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10088914
Downloads since deposit
10Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item