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
| Verfasserangaben: | Henning BordihnORCiD |
|---|---|
| ISSN: | 0304-3975 |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Jahr der Erstveröffentlichung: | 2004 |
| Erscheinungsjahr: | 2004 |
| Datum der Freischaltung: | 24.03.2017 |
| Quelle: | Theoretical Computer Science. - ISSN 0304-3975. - 314 (2004), 3, S. 445 - 449 |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| Peer Review: | Referiert |
| Name der Einrichtung zum Zeitpunkt der Publikation: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |
