Journal article
Context-free commutative grammars with integer counters and resets
- 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 $\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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 303.0KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.tcs.2016.06.017
Authors
- Publisher:
- Elsevier
- Journal:
- Theoretical Computer Science More from this journal
- Publication date:
- 2016-06-01
- Acceptance date:
- 2016-06-10
- DOI:
- Keywords:
- Pubs id:
-
pubs:616395
- UUID:
-
uuid:08f16169-349f-4857-98de-0b9ce5bd4c6e
- Local pid:
-
pubs:616395
- Source identifiers:
-
616395
- Deposit date:
-
2016-07-22
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2016
- Notes:
- © 2016 Elsevier B.V. All rights reserved.
If you are the owner of this record, you can report an update to it here: Report update to this record