کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436991 | 690059 | 2012 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 454, 5 October 2012, Pages 129-135