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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2016
|
| _version_ | 1826258114472574976 |
|---|---|
| author | Chistikov, D Haase, C Halfon, S |
| author_facet | Chistikov, D Haase, C Halfon, S |
| author_sort | Chistikov, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:28:54Z |
| format | Journal article |
| id | oxford-uuid:08f16169-349f-4857-98de-0b9ce5bd4c6e |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:28:54Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:08f16169-349f-4857-98de-0b9ce5bd4c6e2022-03-26T09:15:38ZContext-free commutative grammars with integer counters and resetsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:08f16169-349f-4857-98de-0b9ce5bd4c6eSymplectic Elements at OxfordElsevier2016Chistikov, DHaase, CHalfon, SWe 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. |
| spellingShingle | Chistikov, D Haase, C Halfon, S Context-free commutative grammars with integer counters and resets |
| title | Context-free commutative grammars with integer counters and resets |
| title_full | Context-free commutative grammars with integer counters and resets |
| title_fullStr | Context-free commutative grammars with integer counters and resets |
| title_full_unstemmed | Context-free commutative grammars with integer counters and resets |
| title_short | Context-free commutative grammars with integer counters and resets |
| title_sort | context free commutative grammars with integer counters and resets |
| work_keys_str_mv | AT chistikovd contextfreecommutativegrammarswithintegercountersandresets AT haasec contextfreecommutativegrammarswithintegercountersandresets AT halfons contextfreecommutativegrammarswithintegercountersandresets |