Transcript P Systems with Antiport Rules for Evolution Rules

Tissue P Systems with Small
Numbers of Symbols and Cells
Artiom ALHAZOV
Rudolf FREUND
Marion OSWALD
Faculty of Informatics
Vienna University of Technology
Wien, Austria
Overview
P Systems with Symport/Antiport Rules
● membrane systems / P systems - definition
● complexity issues
● selected results for P systems
Tissue P Systems with Symport/Antiport
Rules
● definition
● complexity issues
● results for tissue P systems
Summary and Open Problems
Membrane Systems (P Systems)
(invented by Gheorghe PǍUN , 1998)
membrane structure
multisets of objects
evolution / communication rules applied in
• the maximally parallel mode
• the sequential mode
many variants computationally complete
Gheorghe Păun: Membrane Computing An Introduction. Springer-Verlag, Berlin, 2002.
The P Systems Web Page:
http://psystems.disco.unimib.it
Membrane structure [1 [2 [4 ]4 [5 ]5 ]2 [3 ]3 ]1
elementary
membrane
region
4
5
2
3
skin membrane 1
P system with symport/antiport rules
( O,  ,w1, ... , wn, E, R1, ... , Rn, i0 )
O alphabet of objects (symbols);
 membrane structure with n membranes;
wi , 1  i  n, multiset over V in region i;
E  V set of objects in the environment;
Ri , 1  i  n, finite set of symport rules
(x,in) or (x,out) and antiport rules (x,out;y,in)
over V, x,y  O+ assigned to membrane i;
i0 output membrane.
derivation modes
maximally parallel derivation mode
choose a multiset of rules in such a way that after
assigning objects from the environment and the
regions to these rules not enough objects are left
to add another rule which could be applied
together with the chosen rules.
sequential derivation mode
only one rule is applied in each derivation step.
P system – derivation
A derivation in the P system  works as follows:
We start with the initial multisets wi in the regions
inside the membranes; in the environment, all
elements from E are available in an unbounded
number.
At any stage of the derivation, the rules assigned
to the membranes are used according to the
derivation mode.
P system – language
Every number of objects from O ever appearing
at the end of a halting computation in the ouput
membrane i0 contributes to N(), the language
generated by .
Attention:
in several variants to be found in the literature,
- the ouput membrane i0 must be an elementary
membrane
- by distinguishing between terminal and
nonterminal objects and taking only the
terminal objects in the ouput membrane i0
garbage can be “eliminated”
P system – complexity issues
- number of membranes
- number of objects
- weight of the rules
weight of (x,out;y,in) is (|x|,|y|)
- number of rules
- ...
mostly studied in the literature so far:
- number of membranes
- weight of the rules
P systems – classic results
Theorem. Any recursively enumerable
language L can be generated by a P system with
symport/antiport rules of weight (1,2) and (2,1)
as well as (1,0) with only one membrane
in the maximally parallel derivation mode.
Theorem. P systems with symport/antiport rules
(in an arbitrary membrane structure)
in the sequential derivation mode
exactly generate the matrix languages
(sets of numbers generated by matrix grammars
without appearance checking).
P systems – number of objects
the first result concerning the number of objects
(as well as the number of membranes):
Gh. Păun, J. Pazos, M.J. Pérez Jiménez,
A. Rodríguez-Patón: Symport/ antiport
P systems with three objects are universal;
downloadable from the P Systems Web Page:
http://psystems.disco.unimib.it
three objects and four membranes were needed!
P systems – number of objects, ctd.
Investigations were continued in the Third
Brainstorming Week on Membrane Computing,
Sevilla (Spain), January 31st - February 4th, 2005:
A. Alhazov, R. Freund: P systems with one
membrane and symport / antiport rules of five
symbols are computationally complete.
M.A. Gutierrez-Naranjo, A. Riscos-Nunez,
F.J. Romero-Campero, D. Sburlan (Eds.):
Proceedings of the Third Brainstorming Week on
Membrane Computing, Sevilla (Spain),
January 31st - February 4th, 2005, 19 – 28.
Register machine
M = (n,R,l0,lh)
- n number of registers,
- R finite set of instructions, injectively
labelled with elements from lab(M),
- l0 initial/start label, and
- lh final label.
Register machine – instructions
The instructions are of the following forms:
- l1:(ADD(r), l2, l3) Add 1 to the contents of
register r and proceed to instruction l2 or l3.
- l1:(SUB(r), l2, l3) If register r is not empty,
then subtract 1 from its contents and go to
instruction l2, otherwise proceed to
instruction l3 .
- lh:halt Stop the machine.
P systems – number of objects,
newest results
A. Alhazov, R. Freund, M. Oswald:
Symbol/Membrane Complexity of P Systems with
Symport / Antiport Rules. Pre-Proceedings
WMC6, Vienna, July 18 – 21, 2005.
Main results:
P systems with symport/antiport rules and
s  2 objects as well as m  1 membranes
can simulate register machines with
max{ m(s-2), (m-1)(s-1) } registers
(equality in case of s = m+1).
P Systems with Antiport Rules and a
Small Number of Objects and Membranes
objects
NRE
5
2
NRE
(new)
at least
undecid.
at least
NREG
1
NFIN
4
3
1
2
3
4
5
6 membranes
Tissue P System
(m, O, w1,... ,wn, E, ch, (R(i,j))(i,j) ch, i0 )
m number of cells;
O alphabet of objects (symbols);
wi , 1  i  n, multiset over V in cell i;
E  V set of objects in the environment;
ch set of channels between cells (environment)
R(i,j) , (i,j) ch, finite set of symport/antiport rules
over O, x,y  O+ assigned to channel (i,j);
we simply write x/y for the rules;
i0 output cell.
Tissue P System – conventions
cells with an arbitrary graph structure for the
connections between cells (not necessarily a tree
as in P systems) and cells with the environment
Conventions:
E = V all objects are available in an unlimited
number in the environment;
(i,j) ch implies i  j
i0 = 1 the first cell is always the output cell.
(m, O, w1,... ,wn, ch, (R(i,j))(i,j) ch)
Tissue P System – derivations
A derivation in the P system  works as follows:
We start with the initial multisets wi in the cells.
In each derivation step,
all channels in parallel
execute one symport/antiport rule (if possible).
Tissue P System – languages
Every number of objects from O ever appearing
at the end of a halting computation in the ouput
cell 1 contributes to N(), the language
generated by .
NOnt’Pm
and
NOntPm
family of languages (sets of natural numbers)
generated by tissue P systems with n objects and
m cells /
with only one channel out of { (i,j), (j,i) }
for each pair (i,j) with i  j.
Tissue P System – example 1
Let L be an arbitrary finite set of natural numbers.
 = ( 1, {a}, w1, { (1,0) }, R(1,0) )
w1 = am
m := max { i | ai  L } +1
R(1,0) = {am /ai | ai  L }
N() = L
1
Tissue P System – example 2
G = ({ Xi | 1  i  n }, { a }, P, X1 )
regular grammar over one-letter alphabet { a };
productions in P of the form Xi  aXj and Xn  .
 = ( 2, {a}, , aa, { (0,2), (2,0), (2,1) },
R(0,2), R(2,0), R(2,1) )
R(2,0) = { a2i /a2j+1 | Xi  aXj  P }
R(0,2) = { a2n+2 /a }, R(2,1) = { a/ },
N() = Ps(L(G))
1
2
Tissue P system – complexity issues
- number of cells
- number of objects
- weight of the rules
weight of x/y is (|x|,|y|)
- number of rules
- ...
mostly studied in the literature so far:
- number of cells
- weight of the rules
Tissue P systems – number of objects
the first result concerning the number of objects
(as well as the number of cells):
R. Freund, M. Oswald: Tissue P systems with
symport / antiport rules of one symbol are
computationally complete;
downloadable from the P Systems Web Page:
http://psystems.disco.unimib.it
Theorem. NRE = NO1t‘P6 = NO1tP7
Tissue P systems – number of objects
newest results
Theorem. NRE = NO2t‘P3
Theorem. NRE = NO2tP3 !!
Theorem. NRE = NO3t‘P2
Theorem. NRE = NO4tP2
Tissue P systems – number of objects
proof ideas
- simulate register machine
- encode the labels di+1 of the register machine
as powers of a symbol p in such a way that
 the sum of two codes is larger than the
largest code c(lh), lh = d(t-1)+1;
 the distance g between two codes allows
for using one symbol p for appearance
checking and numbers of p > 1 to detect an
incorrect application of rules (g=3 sufficient);
linear encoding c(x) = gx + gdt
Tissue P systems – number of objects
results for one cell
Theorem. NRE = NO5t‘P1
Theorem. NREG = NOntP1 for n  2
Theorem. NFIN = NO1tP1
tP Systems with Antiport Rules and a
Small Number of Objects and Cells
objects
NRE
5
NREG
4
2
at least
NREG
>
NFIN
1
NFIN
3
1
2
3
4
5
6
7 cells
t‘P Systems with Antiport Rules and a
Small Number of Objects and Cells
objects
NRE
5
4
at least
NREG
3
2
1
NFIN
1
2
3
4
5
6
7 cells
SUMMARY
► we have shown that only a few cells and
objects are needed to obtain NRE
► with only one channel between a cell and
the environment and with only one cell
we only obtain NREG
► with only one channel between a cell and
the environment we obtain less power than
with two channels between a cell and
the environment
OPEN PROBLEMS
► with only one object, how many cells are
needed to obtain NRE
► with two channels between a cell and
the environment and with only one cell,
how many objects are needed to obtain NRE
► with only two cells,
how many objects are needed to obtain NRE
Workshop on
Membrane Computing
WMC6
will take place in VIENNA
July 18 to 21, 2005
THANK YOU
FOR YOUR ATTENTION