It is shown that every conjunctive language is generated by a conjunctive grammar of a special form, in which every nonterminal A has at most one rule of the general form A ? a1&an, while the rest of the rules for A must be of the type A ? w, where w is a terminal string. For context-free grammars, a similar property does not hold (S. A. Greibach, W. Shi, S. Simonson, "Single tree grammars", 1992).
| Original language | English |
|---|---|
| Title of host publication | SOFSEM 2009 |
| Subtitle of host publication | Theory and Practice of Computer Science - 35th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |
| Pages | 425-436 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 2009 |
| Externally published | Yes |
| Event | 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009 - Spindleruv Mlyn, Czech Republic Duration: 24 Jan 2009 → 30 Jan 2009 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 5404 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 35th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2009 |
|---|---|
| Country/Territory | Czech Republic |
| City | Spindleruv Mlyn |
| Period | 24/01/09 → 30/01/09 |
ID: 78935730