The paper characterizes the family of homomorphisms, under which the deterministic context-free languages, the LL context-free languages and the unambiguous context-free languages are closed. The family of deterministic context-free languages is closed under a homomorphism h if and only if h is either a code of bounded deciphering delay, or the images of all symbols under h are powers of the same string. The same characterization holds for LL context-free languages. The unambiguous context-free languages are closed under h if and only if either h is a code, or the images of all symbols under h are powers of the same string.
| Original language | English |
|---|---|
| Title of host publication | Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings |
| Pages | 154-165 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 2012 |
| Externally published | Yes |
| Event | 16th International Conference on Developments in Language Theory, DLT 2012 - Taipei, Taiwan, Province of China Duration: 14 Aug 2012 → 17 Aug 2012 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 7410 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 16th International Conference on Developments in Language Theory, DLT 2012 |
|---|---|
| Country/Territory | Taiwan, Province of China |
| City | Taipei |
| Period | 14/08/12 → 17/08/12 |
ID: 78945231