35 citations · 169 across the 13 of their papers we have counts for
4 papers · 1 filter
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…
Approaching the Coverability Problem Continuously
Michael Blondin, Alain Finkel, Christoph Haase +1
The coverability problem for Petri nets plays a central role in the verification of concurrent shared-memory programs. However, its high EXPSPACE-complete complexity poses a challe…
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…
The Complexity of the Kth Largest Subset Problem and Related Problems
Christoph Haase, Stefan Kiefer
We show that the Kth largest subset problem and the Kth largest m-tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literat…