Context-Free Commutative Grammars with Integer Counters and Resets

2015/11/16 by Chistikov, Dmitry, Haase, Christoph, Halfon, Simon · 1 citation
#F.1.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1511.04893

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 problem is, in general, coNEXP-complete and already Π₂^P-complete for grammars with only one non-terminal symbol. Showing the lower bound for the latter result requires us to develop a novel Π₂^P-complete variant of the classic subset sum problem.

Cited by

• LogiCase: Effective Test Case Generation from Logical Description in Competitive Programming

Related

• Tightening the Complexity of Equivalence Problems for Commutative Grammars
• Complexity of Problems for Commutative Grammars
• On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
• Multiplicity Problems on Algebraic Series and Context-Free Grammars
• A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity