Affiliations: Research Group on Mathematical Linguistics Rovira i
Virgili University and Institute of Mathematics and Computer Science Academy of
Sciences of Moldova. E-mail: [email protected] | Faculty of Informatics Vienna University of
Technology, Austria. E-mail: {rudi,marion}@emcc.at | Dipartimento di Informatica Sistemistica e
Comunicazione Università degli Studi di Milano-Bicocca, Italy. E-mail:
[email protected] | Dip. di Inf. Sistemistica e Comunicazione
Università degli Studi di Milano-Bicocca, Italy. E-mail:
[email protected]
Abstract: We introduce a new variant of membrane systems where the rules are
directly assigned to membranes and, moreover, every membrane carries an energy
value that can be changed during a computation by objects passing through the
membrane. The result of a successful computation is considered to be the
distribution of energy values carried by the membranes. We show that for
systems working in the sequential mode with a kind of priority relation on the
rules we already obtain universal computational power. When omitting the
priority relation, we obtain a characterization of the family of Parikh sets of
languages generated by context-free matrix grammars. On the other hand, when
using the maximally parallel mode, we do not need a priority relation to obtain
computational completeness. Finally, we introduce the corresponding model of
tissue P systems with energy assigned to the membrane of each cell and objects
moving from one cell to another one in the environment as well as being able to
change the energy of a cell when entering or leaving the cell. In each
derivation step, only one object may pass through the membrane of each cell.
When using priorities on the rules in the sequential mode (where in each
derivation step only one cell is affected) as well as without priorities in the
maximally parallel mode (where in each derivation step all cells possible are
affected) we again obtain computational completeness, whereas without
priorities on the rules in the sequential mode we only get a characterization
of the family of Parikh sets of languages generated by context-free matrix
grammars.
Keywords: computational completeness, matrix grammars, membrane computing, P systems
