Star-Free Languages are Church-Rosser Congruential
Star-Free Languages are Church-Rosser Congruential
复制标题
无星语言是 Church-Rosser 一致的
DOI：
10.1016/j.tcs.2012.01.028
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
P. Weil
中科院分区：
文献类型：
--
作者：
V. Diekert;Manfred Kufleitner;P. Weil
Church-Rosser同余语言是由McNaughton、Narendran和Otto在1988年提出的。一个语言L是Church-Rosser同余的（属于CRCL），如果存在一个有限的、合流的、长度缩减的半图厄系统S，使得L是模S的同余类的有限并。到目前为止，是否每一种常规语言都在CRCL中仍然是开放的。在本文中，我们证明了每一个无星语言都在CRCL中。事实上，我们证明了一个更强的陈述：对于每一个无星语言L，存在一个有限的、合流的、子字缩减的半图厄系统S，使得模S的同余类的总数是有限的，并且使得L是模S的同余类的并集。实践证明，该结构是有效的。
The class of Church–Rosser congruential languages has been introduced by McNaughton, Narendran, and Otto in 1988. A language L is Church–Rosser congruential (belongs to CRCL), if there is a finite, confluent, and length-reducing semi-Thue system S such that L is a finite union of congruence classes modulo S. To date, it is still open whether every regular language is in CRCL. In this paper, we show that every star-free language is in CRCL. In fact, we prove a stronger statement: for every star-free language L there exists a finite, confluent, and subword-reducing semi-Thue system S such that the total number of congruence classes modulo S is finite and such that L is a union of congruence classes modulo S. The construction turns out to be effective.