On the Power of Parallel Communicating

Grammar Systems

György Vaszil

Computer and Automation Research Institute

Hungarian Academy of Sciences

Kende u. 13-17, H-1111 Budapest, Hungary

Parallel communicating grammar systems, introduced in [5], are formal language theoretic models of parallel and distributed computation. In these systems several grammars are working on their own sentential forms in parallel and their work is organized in a communicating system to generate a single language.

PC grammar systems have been the subject of detailed study over the past few years, see [1],[4]. Here we report on new results from [3],[2] and [6], concerning the generative power of PC grammar systems with context-free rules. We show that these systems generate all recursively enumerable languages, by demonstrating how they can simulate two-counter machines, a restricted but computationally complete class of Turing machines.

References

1 E. Csuhaj-Varj?u, J. Dassow, J. Kelemen, Gh. P<=aun, Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London, 1994.

2 E. Csuhaj-Varj?u, Gy. Vaszil, On synchronization in context-free PC grammar systems, submitted, 1997.

3 E. Csuhaj-Varj?u, Gy. Vaszil, Context-free PC grammar systems are computationally complete, submitted, 1997.

4 J. Dassow, Gh. P<=aun, G. Rozenberg, Grammar Systems. Chapter 4. Handbook of Formal

Languages, ed. by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin, 1997, 155-213.

5 Gh. P<=aun, L. Santean, Parallel communicating grammar systems: the regular case, Ann. Univ. Bucharest, Ser. Matem.-Inform. 38, 2 (1989), 55-63.

6 Gy. Vaszil, On parallel communicating Lindenmayer systems, In: Grammatical Models of Multi-

Agent Systems (Gh. P<=aun, A. Salomaa, eds.), Gordon and Breach Science Publishers, to appear.

Workshop 19 Stuttgart, January 1998

Seite 19: vorherige Seite | Übersicht