Affiliations: Computer and Automation Research Institute, Hungarian
Academy of Sciences, Kende utca 13–17, H-1111 Budapest, Hungary.
E-mail: {csuhaj,vaszil}@sztaki.hu | Institute of Mathematics of the Romanian Academy PO
Box 1-764, 014700 Bucureşti, Romania, and Research Group on Natural
Computing Department of Computer Science and Artificial Intelligence,
University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain.
E-mails: [email protected]; [email protected]
Abstract: In this paper we discuss some relationships between grammar systems
and P systems (membrane systems), two areas of computer science dealing with
distributed computing models, but with different motivations and different
types of basic ingredients. We extend one of the most important communication
protocols of cooperating distributed (CD) grammar systems, the so-called
t-derivation mode, to P systems with string-objects: if no rule can be applied
to a string in a region of a P system, then the string is moved to a
neighbouring region, depending on the communication mode either in exactly one
direction (in or out) or in both directions. We describe the computational
power of the obtained classes of P systems in comparison with families of
languages generated by grammars in the Chomsky hierarchy or with CD grammar
systems and formulate several problems for future research.
Keywords: Cooperating distributed grammar systems, P systems
