Article (Scientific journals)
Inverse star, borders, and palstars
Rampersad, Narad; Shallit, Jeffrey; Wang, Ming-wei
2011In Information Processing Letters, 111, p. 420-422
Peer Reviewed verified by ORBi
 

Files


Full Text
palstars_arx.pdf
Author preprint (86.43 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[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.
Disciplines :
Mathematics
Author, co-author :
Rampersad, Narad ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Shallit, Jeffrey
Wang, Ming-wei
Language :
English
Title :
Inverse star, borders, and palstars
Publication date :
2011
Journal title :
Information Processing Letters
ISSN :
0020-0190
Publisher :
Elsevier Science
Volume :
111
Pages :
420-422
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 04 May 2011

Statistics


Number of views
51 (2 by ULiège)
Number of downloads
130 (0 by ULiège)

Scopus citations®
 
8
Scopus citations®
without self-citations
1
OpenCitations
 
6

Bibliography


Similar publications



Contact ORBi