TY  - JOUR
A1  - Bordihn, Henning
T1  - Context-freeness of the power of context-free languages is undecidable
N2  - The power of a language L is the set of all powers of the words in L. In this paper, the following decision problem is investigated. Given a context-free language L, is the power of L context-free? We show that this problem is decidable for languages over unary alphabets, but it is undecidable whenever languages over alphabets with at least two letters are considered. (C) 2003 Elsevier B.V. All rights reserved
Y1  - 2004
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/15062
SN  - 0304-3975
ER  -