Parikh Images of Grammars: Complexity and Applications

Abstract

Parikh’s Theorem states that semilinear sets are effectively equivalent with the Parikh images of regular languages and those of context-free languages. In this paper, we study the complexity of Parikh’s Theorem over any fixed alphabet size d. We prove various normal form the oremsin the case of NFAs and CFGs. In particular, the normalform theorems ensure that a union of linear sets with dgenerators suffice to express such Parikh images, which in the case of NFAs can further be computed in polynomial time. We then apply apply our results to derive: (1) optimal complexity for decision problems concerning Parikh images(e.g. membership, universality, equivalence, and disjointness), (2) a new polynomial fragment of integer programming, (3) an answer to an open question about PAC-learnability of semilinear sets, and (4) an optimal algorithm for verifying LTL over discrete-timed reversal-bounded counter systems.