35 citations · 169 across the 13 of their papers we have counts for
Showing 2015 · cs.FLShow all
2 papers · 2 filters
cs.FL2015
Context-Free Commutative Grammars with Integer Counters and Resets
Dmitry Chistikov, Christoph Haase, Simon Halfon
We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on…
cs.FL2015★ 3 cited
Tightening the Complexity of Equivalence Problems for Commutative Grammars
Christoph Haase, Piotr Hofman
We show that the language equivalence problem for regular and context-free commutative grammars is coNEXP-complete. In addition, our lower bound immediately yields further coNEXP-c…