Word Problems - This Time with Interleaving
Word Problems - This Time with Interleaving
复制标题
DOI：
10.21236/ada240494
复制
发表时间：
1991-06
期刊：
影响因子：
--
通讯作者：
Alain J. Mayer;L. Stockmeyer
中科院分区：
文献类型：
--
作者：
Alain J. Mayer;L. Stockmeyer
摘要：我们考虑了用交织算子扩展的正则表达式，并研究了这些表达式的成员关系的复杂性和不等价性问题。对于使用联合、连接、Kleene star和交织的表达式，我们证明了不等价问题(判断两个给定的表达式是否描述同一组单词)对于指数空间是完备的。在没有Kleene star的情况下，我们证明了对于多项式时间族的第二水平上的某一类，不等价问题是完全的。成员资格问题的某些情况(决定一个给定的单词是否在给定的表达式所描述的语言中)被证明是NP完全的。文中还讨论了可在多项式时间内求解的隶属度问题的特例。
Abstract : We consider regular expressions extended with the interleaving operator, and investigate the complexity of membership and inequivalence problems for these expressions. For expressions using the operators union, concatenation, Kleene star, and interleaving, we show that the inequivalence problem (deciding whether two given expressions do not describe the same set of words) is complete for exponential space. Without Kleene star, we show that the inequivalence problem is complete for a certain class at the second level of the polynomial-time hierarchy. Certain cases of the membership problem (deciding whether a given word is in the language described by a given expression) are shown to be NP-complete. Special cases of the membership problem which can be solved in polynomial time are also discussed.