Context-free commutative grammars with integer counters and resets

Journal article

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 $\Pi_2^\text{P}$-complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel $\Pi_2^\text{P}$-complete variant of the classic subset sum problem.

Authors: Chistikov, D; Haase, C; Halfon, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Publication date: 2016-06-01
• Acceptance date: 2016-06-10
• DOI: 10.1016/j.tcs.2016.06.017
• Keywords: subset sum; Presburger arithmetic; vector addition systems with states; reset nets; communication-free Petri nets; context-free commutative grammars