Some Regular Languages That Are Church-Rosser Congruential
Some Regular Languages That Are Church-Rosser Congruential
复制标题
一些与 Church-Rosser 一致的常规语言
DOI：
10.1007/3-540-46011-x_29
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Johannes Waldmann
中科院分区：
文献类型：
--
作者：
Gundula Niemann;Johannes Waldmann
在1988年，McNaughton等人引入了Church-Rosser同余语言的类CRCL，作为一种通过合流长度缩减的字符串重写系统来定义形式语言的方法。与其他全等语言类一样，CRCL是相当有限的，尽管它包含一些不是上下文无关的语言。2000年，尼曼证明了至少每一个具有多项式密度的正则语言都是Church-Rosser同余的。正则语言类是否包含在CRCL中仍然是一个悬而未决的问题。在这里，我们给出了一些家庭的正规语言的指数密度是丘奇-罗瑟同余。更确切地说，我们表明，一些洗牌语言，以及1级的Straubing-Therien层次结构，在CRCL，使用一个充分条件下，一个正规的语言是丘奇-罗瑟同余。最后，我们给出了一个Church-Rosser全等的群语言族，但不满足这个条件。
In 1988 McNaughton et al introduced the class CRCL of Church-Rosser congruential languages as a way to define formal languages by confluent length-reducing string-rewriting systems. As other congruential language classes CRCL is quite limited, although it contains some languages that are not contextfree. In 2000 Niemann has shown that at least each regular language with polynomial density is Church-Rosser congruential. It is still an open question whether the class of regular languages is contained in CRCL. Here we give some families of regular languages of exponential density that are Church-Rosser congruential. More precisely, we show that some shuffle languages, as well as Level 1 of the Straubing-Therien hierarchy, are in CRCL, using a sufficient condition under which a regular language is Church-Rosser congruential. Last, we give a family of group languages that are Church-Rosser congruential, but do not fulfill this condition.