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.
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-pp.ucl.ac.uk/id/eprint/10088914 |
Archive Staff Only
 |
View Item |
