Star-Free Languages are Church-Rosser Congruential

Details Star-Free Languages are Church-Rosser Congruential Star-Free Languages are Church-Rosser Congruential

2011-11-18

arxiv.org/abs/1111.4300v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Star-Free Languages are Church-Rosser Congruential does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Star-Free Languages are Church-Rosser Congruential, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Star-Free Languages are Church-Rosser Congruential will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-548862