论文标题
关于明确无上下文语法的普遍性和包容性问题的复杂性
On the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars
论文作者
论文摘要
我们研究了明确的有限自动机和无上下文语法的普遍性和包容性问题的计算复杂性。我们观察到，对于明确的无上下文语法，可以将几个这样的问题简化为普遍性问题。长期以来，已知后一个问题是可决定的，我们提出了一种Pspace算法，该算法通过还原到卷积的复发方程问题而起作用。我们不知道任何非平凡的复杂性下限。但是，我们表明，对于长期存在的开放问题SQRTSUM，很难计算出明确的无上下文语言的硬发量量度，即通用性的定量概括。
We study the computational complexity of universality and inclusion problems for unambiguous finite automata and context-free grammars. We observe that several such problems can be reduced to the universality problem for unambiguous context-free grammars. The latter problem has long been known to be decidable and we propose a PSPACE algorithm that works by reduction to the zeroness problem of recurrence equations with convolution. We are not aware of any non-trivial complexity lower bounds. However, we show that computing the coin-flip measure of an unambiguous context-free language, a quantitative generalisation of universality, is hard for the long-standing open problem SQRTSUM.
