Selected publications at LSV

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 ΠP2-complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel ΠP2-complete variant of the classic subset sum problem.

@techreport{CHH-arxiv16,
   author = {Chistikov, Dmitry and Haase, Christoph and Halfon, Simon},
   institution = {Computing Research Repository},
   month = nov,
   note = {31~pages},
   number = {1511-04893},
   type = {Research Report},
   title = {Context-Free Commutative Grammars with Integer Counters and Resets},
   url = {http://arxiv.org/abs/1511.04893},
   year = {2015},
}

About LSV

Select by Year