Reference : Inverse star, borders, and palstars
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Inverse star, borders, and palstars
Rampersad, Narad mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Shallit, Jeffrey [ > > ]
Wang, Ming-wei [ > > ]
Information Processing Letters
Elsevier Science
Yes (verified by ORBi)
[en] 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.

File(s) associated to this reference

Fulltext file(s):

Open access
palstars_arx.pdfAuthor preprint84.41 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.