[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
Solution by O.P. Lossers Problem 94-20 SIAM Review 37 1995 619 620
J. Brzozowski Roots of star events J. ACM 14 1967 466 477
J. Brzozowski, E. Grant, and J. Shallit Closures in formal languages and Kuratowski's theorem V. Diekert, D. Nowotka, Developments in Language Theory, 13th International Conference, DLT 2009 Lecture Notes in Computer Science vol. 5583 2009 Springer-Verlag 125 144
H. Harborth Endliche 0-1-Folgen mit gleichen Teilböcken J. Reine Angew. Math. 271 1974 139 154
D.E. Knuth, J. Morris, and V. Pratt Fast pattern matching in strings SIAM J. Comput. 6 1977 323 350
P.T. Nielsen A note on bifix-free sequences IEEE Trans. Inform. Theory IT-19 1973 704 706
W. Ogden A helpful result for proving inherent ambiguity Math. Syst. Theory 2 1968 191 194
M. Régnier Enumeration of bordered words: le langage de la Vache-qui-Rit RAIRO Theor. Inform. Appl. 26 1992 303 317
D.M. Silberger How many unbordered words? Ann. Soc. Math. Polon. Ser. 1 Commentat. Math. 22 1980 143 145
I. Simon String matching algorithms and automata J. Karhumäki, H. Maurer, G. Rozenberg, Results and Trends in Theoretical Computer Science Lecture Notes in Computer Science vol. 812 1994 Springer 386 395