Context-freeness of the power of context-free languages is undecidable
- 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
| Author details: | Henning BordihnORCiD |
|---|---|
| ISSN: | 0304-3975 |
| Publication type: | Article |
| Language: | English |
| Year of first publication: | 2004 |
| Publication year: | 2004 |
| Release date: | 2017/03/24 |
| Source: | Theoretical Computer Science. - ISSN 0304-3975. - 314 (2004), 3, S. 445 - 449 |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| Peer review: | Referiert |
| Institution name at the time of the publication: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
