The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL
The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL
复制标题
具有交集的正则表达式的隶属度问题在 LOGCFL 中完成
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
H. Petersen
中科院分区：
文献类型：
--
作者：
H. Petersen
我们证明了上下文无关语言的识别问题可以通过具有线性输出长度的对数空间约简来简化为由正则表达式定义的语言中的隶属关系。我们还展示了一个匹配上界，改进了已知的事实，即这些正则表达式的隶属性问题是在NC2中。这些结果共同证明了LOGCFL的隶属度问题是完整的。对于一元表达式，我们给出了NL类的硬度和一些相关的结果。
We show that the recognition problem of context-free languages can be reduced to membership in the language defined by a regular expression with intersection by a log space reduction with linear output length. We also show a matching upper bound improving the known fact that the membership problem for these regular expressions is in NC2. Together these results establish that the membership problem is complete in LOGCFL. For unary expressions we show hardness for the class NL and some related results.