Context-free commutative grammars with integer counters and resets
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 ...Expand abstract
- Publication status:
- Peer review status:
- Peer reviewed
- Accepted manuscript
- Copyright holder:
- Elsevier B.V.
- Copyright date:
- © 2016 Elsevier B.V. All rights reserved.
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record