Parallel communicating grammar systems : recent results, open problems

Păun Gheorghe: Parallel communicating grammar systems : recent results, open problems. In: Acta cybernetica, (12) 4. pp. 381-395. (1996)

[thumbnail of cybernetica_012_numb_004_381-395.pdf]
Cikk, tanulmány, mű

Download (841kB) | Preview


First, we recall several recent results concerning the generative power of parallel communicating (PC) grammar systems, including characterizations of recursively enumerable (RE) languages starting from PC grammar systems and their languages. Then, we prove that the simple matrix languages can be generated by PC grammar systems and finally we introduce a new class of PC grammar systems: when a component has to communicate, it may transmit any non-empty prefix of its current sentential form. Each RE language is the morphic image of the intersection with a regular language of a language generated by such a system. A series of open problems are pointed out in this context.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1996
Volume: 12
Number: 4
ISSN: 0324-721X
Page Range: pp. 381-395
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 393-395. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 14:51

Actions (login required)

View Item View Item