ROMANIAN JOURNAL OF INFORMATION SCIENCE AND
TECHNOLOGY
Volume 4, Numbers 1-2, 2001, 171 - 182
P Systems with Immediate Communication
Carlos MARTIN-VIDE1,
Gheorghe PAUN2*,
Alfonso RODRIGUEZ-PATÓN3**
1Research Group on Mathematical Linguistics,
Rovira i Virgili University, Tarragona, Spain
2Institute of Mathematics of the Romanian Academy, Bucharest, Romania
3 Department of Artificial Intelligence, Faculty of Computer Science,
Politechnical University of Madrid, Madrid, Spain
Abstract.
In the
attempt to define P systems with the communication of objects through membranes controlled
in an as simple as possible manner, we consider the case of string-objects (processed by
rewriting or by splicing) with immediate communication: the string obtained by
applying an evolution rule is immediately moved from the region where it is obtained to
one of the neighboring regions, nondeterministically chosen. Rewriting P systems of this
type (and without other controls on the communication or the rule application) are shown
to generate only matrix languages, while for splicing P systems we obtain again the usual
result from membrane system area: computational universality (that is, a characterization
of recursively enumerable languages).
*Work supported by a grant of NATO Science Committee, Spain, 2000--2001, and by
Facultad de Informatica, Universidad Politecnica de Madrid.
**Work supported by Turku Center for Computer Science, Finland, and by a grand of
Facultad de Informatica, Universidad Politecnica de Madrid. |