Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
The famous theorem by Chomsky and Schützenberger ("The algebraic theory of context-free languages", 1963) states that every context-free language is representable as h(D k ∩ R), where D k is the Dyck language over k ≥ pairs of brackets, R is a regular language and h is a homomorphism. This paper demonstrates that one can use a non-erasing homomorphism in this characterization, as long as the language contains no one-symbol strings. If the Dyck language is augmented with neutral symbols, the characterization holds for every context-free language using a letter-to-letter homomorphism.
Original language | English |
---|---|
Title of host publication | Developments in Language Theory - 16th International Conference, DLT 2012, Proceedings |
Pages | 121-129 |
Number of pages | 9 |
DOIs | |
State | Published - 20 Aug 2012 |
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: 41139545