Shuffle Quotient and Decompositions

Shuffle Quotient and Decompositions
复制标题

洗牌商和分解

DOI：
10.1007/3-540-46011-x_15
复制
发表时间：
2001
期刊：
J. ACM
影响因子：
--
通讯作者：
S. Vágvölgyi
S. Vágvölgyi
中科院分区：
--
文献类型：
--
作者：
C. Câmpeanu;K. Salomaa;S. Vágvölgyi

文献摘要

被引文献

相似文献

我们引入了一个右同余关系，这是类比的Nerode同余时，连锁被替换为洗牌。使用这个关系，我们表明对于正则语言的某些子类，洗牌分解问题是可判定的。我们表明，洗牌分解是不可判定的上下文无关的语言。
We introduce a right congruence relation that is the analogy of the Nerode congruence when catenation is replaced by shuffle. Using this relation we show that for certain subclasses of regular languages the shuffle decomposition problem is decidable. We show that shuffle decomposition is undecidable for context-free languages.