Reference : Inverse star, borders, and palstars
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/90087
Inverse star, borders, and palstars
English
Rampersad, Narad mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Shallit, Jeffrey [ > > ]
Wang, Ming-wei [ > > ]
2011
Information Processing Letters
Elsevier Science
111
420-422
Yes (verified by ORBi)
0020-0190
[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.
http://hdl.handle.net/2268/90087

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
palstars_arx.pdfAuthor preprint84.41 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.