Inverse Star, Borders, and Palstars

Details Inverse Star, Borders, and Palstars Inverse Star, Borders, and Palstars

2010-08-14

arxiv.org/abs/1008.2440v2

Computer Science

Formal Languages and Automata Theory

revised to take into account Brzozowski article

Scientific paper

A language L is closed if L = L*. We consider an operation on closed languages, L-*, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L-* is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.

Affiliated with

Also associated with

No associations

Rating

Inverse Star, Borders, and Palstars 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 Inverse Star, Borders, and Palstars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inverse Star, Borders, and Palstars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42431