@article{CHISTIKOV2018147,
    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.},
    Author = {Chistikov, Dmitry and Haase, Christoph and Halfon, Simon},
    File = {Context-free commutative grammars with integer counters and resets - 1-s2.0-S0304397516302535-main - a - a - b.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {Context-free commutative grammars, Communication-free Petri nets, Reset nets, Vector addition systems with states, Presburger arithmetic, Subset sum},
    Note = {Reachability Problems 2014: Special Issue},
    Pages = {147 - 161},
    Title = {Context-free commutative grammars with integer counters and resets},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397516302535},
    Volume = {735},
    Year = {2018},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397516302535},
    bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2016.06.017},
    date-added = {2020-03-03 16:26:09 +0100},
    date-modified = {2020-03-03 16:26:09 +0100},
    doi = {10.1016/j.tcs.2016.06.017}
}

@article{CHISTIKOV2018147, 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.}, Author = {Chistikov, Dmitry and Haase, Christoph and Halfon, Simon}, File = {Context-free commutative grammars with integer counters and resets - 1-s2.0-S0304397516302535-main - a - a - b.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {Context-free commutative grammars, Communication-free Petri nets, Reset nets, Vector addition systems with states, Presburger arithmetic, Subset sum}, Note = {Reachability Problems 2014: Special Issue}, Pages = {147 - 161}, Title = {Context-free commutative grammars with integer counters and resets}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397516302535}, Volume = {735}, Year = {2018}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397516302535}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2016.06.017}, date-added = {2020-03-03 16:26:09 +0100}, date-modified = {2020-03-03 16:26:09 +0100}, doi = {10.1016/j.tcs.2016.06.017} }