PC grammar systems with five context-free components generate all recursively enumerable languages
| Title | PC grammar systems with five context-free components generate all recursively enumerable languages |
| Publication Type | Journal Papers |
| Year of Publication | 2003 |
| Authors | Csuhaj-Varjú, E., Paun G., & Vaszil G. |
| Journal Title | Theoretical Computer Science |
| Publisher | Elsevier |
| Place Published | Amsterdam (The Netherlands) |
| Volume | 299 |
| Pages | 785 - 794 |
| Abstract | Parallel communicating grammar systems (PC grammar systems, in short) are language generating devices consisting of several context-free grammars which work synchronously on their own sentential forms and communicate the generated strings to each other by request. These systems with eleven components are known to have the power of the Turing machines. We considerably improve this result, proving that five components suffice in order to generate any recursively enumerable language. |
| Keywords | descriptional complexity, parallel communicating grammar systems, recursively enumerable languages |
| Issue | 1-3 |
| ISSN Number | 0304-3975 |
| DOI | 10.1016/S0304-3975(02)00852-6 |
Research Group on Natural Computing (PAI - TIC 193)
Department of Computer Science and Artificial Intelligence
University of Seville
Webmasters: the members of the RGNC
| Follow us: |  |
 |
|
Featured News: |
|
Mario J. Pérez-Jiménez in the top 2% of scientists of the World |
|
Agustín became Full Professor |
|
Science names our most recent research project |