Parikh Images of Grammars: Complexity and Applications
Parikh Images of Grammars: Complexity and Applications
复制标题
帕里克语法图：复杂性和应用
DOI：
10.1109/lics.2010.21
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Lin
中科院分区：
文献类型：
--
作者：
Eryk Kopczynski;A. Lin
Parikh的定理指出，半线性集有效地等于普通语言和无上下文语言的图像。 OREMS在NFA和CFG的情况下。 NFA的情况可以在多项式时间内进一步计算。在整数编程中，（3）关于半连接组的PAC可行性的开放问题的答案，以及（4）一种用于验证LTL在离散的反向反向计数器系统上验证LTL的最佳算法。
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.