✦ LIBER ✦
PC grammar systems with five context-free components generate all recursively enumerable languages
✍ Scribed by Erzsébet Csuhaj-Varjú; Gheorghe Păun; György Vaszil
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 143 KB
- Volume
- 299
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
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 ÿve components su ce in order to generate any recursively enumerable language.