The Library
Context-free commutative grammars with integer counters and resets
Tools
Chistikov, Dmitry, Haase, Christoph and Halfon, Simon (2018) Context-free commutative grammars with integer counters and resets. Theoretical Computer Science, 735 . pp. 147-161. doi:10.1016/j.tcs.2016.06.017 ISSN 0304-3975.
|
PDF
WRAP-context-free-commutative-grammars-integer-Chistikov-2018.pdf - Accepted Version - Requires a PDF viewer. Download (639Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2016.06.017
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 semilinear reachability sets. We also show that the inclusion problem is, in general, coNEXP-complete and already Π P 2 -complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel Π P 2 -complete variant of the classic subset sum problem.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Petri nets, Nets (Mathematics) | |||||||||
Journal or Publication Title: | Theoretical Computer Science | |||||||||
Publisher: | Elsevier Science BV | |||||||||
ISSN: | 0304-3975 | |||||||||
Official Date: | 29 July 2018 | |||||||||
Dates: |
|
|||||||||
Volume: | 735 | |||||||||
Page Range: | pp. 147-161 | |||||||||
DOI: | 10.1016/j.tcs.2016.06.017 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 14 June 2018 | |||||||||
Date of first compliant Open Access: | 14 June 2018 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year