On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
复制标题
关于明确上下文无关语法的普遍性和包含问题的复杂性（技术报告）
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lorenzo Clemente
中科院分区：
文献类型：
--
作者：
Lorenzo Clemente
我们研究了无二义性有限自动机和上下文无关文法的普适性和包含问题的计算复杂性。我们观察到，几个这样的问题可以减少到明确的上下文无关文法的普遍性问题。后一个问题一直被认为是可判定的，我们提出了一个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.
DOI：
10.4230/lipics.stacs.2010.2468
发表时间：
2010
期刊：
ArXiv
影响因子：
--
作者：
Javier Esparza;Andreas Gaiser;Stefan Kiefer
通讯作者：
Stefan Kiefer