Journal article icon

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 ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2016.06.017

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
European Research Council
Funding agency for:
Chistikov, D
Grant:
ImPACT
More from this funder
Name:
Labex Digicosme
Grant:
VERICONISS
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


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP