Transcript slides - CMC11

Polymorphic P Systems
Hiroshima University. Higashi-Hiroshima, Japan
Artiom Alhazov
Sergiu Ivanov
Yurii Rogozhin
repeat N times
{if(STATE=0)increment A
else decrement A;
(code not using STATE)
}
Institute of Mathematics and Computer Science
Academy of Sciences of Moldova
{artiom, sivanov,rogozhin}@math.md
Chişinău, Moldova
Technical University of Moldova
if(STATE=0)INSTR="increment“
else INSTR="decrement";
repeat N times
{INSTR A;
(code not using STATE)
}
Three motives for yet another
extension
• Practical problems need more than just
computational completeness
– Determinism; both input & output
– Proper internal data representation
– Efficiency; complicated data structures
• Von Neumann architecture
– Program is data
• What is a Nucleus in P systems?
– It is inside
– It describes the rules
Main idea
• Most papers changing the active rules
– subsets of a predefined finite set
• What is data?
Try it (time and descriptionally efficiently) with
P systems studied so far
– Multisets in regions
• Most natural way to specify rules as data
– Interpret a pair of regions as a rule
– Contents  left/right side of the rule
• Input: byte (in unary).
aa 1L a 1R
a128
• Output: number of bits 1
2L b 2R
Input over a
s • R={2:anb, 1:nn/2}
Definition: polymorphic P systems
• =(O,T,μ,ws,w1L,w1R,…,wmL,wmR,,iout),
• H={s,1L,1R,…,mL,mR},s=skin,parent(iL)=parent(iR),
• No rules, only features. In this paper :HTar
•
•
•
•
•
Example notation: OPk(polym+d(coo),tar)
+d: disabling rules allowed (by left side=)
coo: cooperative rules
tar: targets allowed (here,inj,out).
k: membrane bound. (thus #rules(k-1)/2)
More definitions
•
•
•
•
•
•
Initial rules are i:wiL(wiR,(i))Rparent(iL)
-d: Regions iL are never empty
Computing: Input O in iin.
D: deterministic (for every input)
Deciding: T={yes,no}, confluent.
Generating - N(), accepting – Na(),
deciding – Nd(), computing a partial
function in the deterministic case – f()
Superexponential growth example
• 1=({a},{a},μ,a,a,a,a,a,a,aa,,1),
• μ=[[]1L[[]2L[[]3L[]3R]2R]1R]s, here.
• In the rest of the talk – graphical notation.
a
a
a
1L
2L
3L aa 3R
a
2R
a
a
Initial rules
R2R={aaa}
R1R={aa}
Rs={aa}
1R
s
skin: a
• Multisets defining rules are changing
• Use “old contents”, i.e.
– compute all, then update
Superexponential - continued
a
a
a
aa 3R
a
2R
a
2L
1L
a
3L
a
⇒n
a
1R
a
1L
s
1
1
1
aa 3R
a2^n
a2^(n(n-1)/2)
a2^(n(n-1)(n-2)/6)
2R
1R
s
Exponential of polynomial
n=10
R1R={aa} R1R={aaa} R1R={aaaaa}
Rs={aa}
Rs={aa}
Rs={aaa}
R2R={aaa}
1024}
R
=
{aa
2
2
1R
2
Rs={aa35184372088832}
x
x
x … 2n
2
4
skin:
a1329227995784915872903807060280344576
1
2
x
x
x … 2(n(n-1)/2)
R2R={aaa} R2R={aaa} R2R={aaa}
2
2L
3L
x
1
x
1
x
…2
n
(n(n-1)(n-2)/6)
Maximal Growth
•
•
•
•
•
•
I: initial number of objects
c: maximum right side size
n: number of steps
d: membrane structure depth
Non-polymorphic systems: Icn
Polymorphic, no targets: Icp(n), deg(p)=d-1
Results
Universality with 47 membranes
Generating without cooperation and without disabling
Factorials with cooperation
Generating even faster with targets
Computing functions
Stay tuned
NOP47(polym-d(coo))=NRE
• [AlhazovVerlan2008]: strongly universal P
system with 1 membrane and 23 rules
• Each rule i:uv becomes [u]iL[v]iR
– total of 47 membranes.
• Focus: efficiency of computations
– e.g., generating/deciding factorials by
constant-time multiplication of variable factors.
Targets. No cooperation
• {n!nk|n1,k0}NOP13(polym-d(ncoo),tar)
a
a
2L
3L
a
c
2R
3R
a
1L
b
b
d
a
4L
5L
6L
1R
4:bbd
2:aa
5:b
3:ac 6:d(a,in )
1R
bd 4R
 5R
a 6R
ab
• b produces copies of d
a
s
1L
a
1R
ab
s
– erased non-deterministically
• d enters 1R as a, increasing n in 1: aan
• The number of objects a in skin is multiplied by n
– Until rule 3 changes rule 1 to can. Non-det.
• If b is erased too soon, multiplication continues
without growing n.
Remarks
• If multiplication stops while n still grows, a
factorial of a smaller number is generated
• The shortest computation generating n!nk
is only n+k+1
• To generate exactly factorials
– We need to stop the multiplication when we
stop the increment
– Seems impossible without cooperative rules.
Exactly factorials
• {n!|n1}NOP9(polym-d(coo),tar)
• Similar to the previous system
• Rule 3 stops both incre2:bbd
3:b(c,in1L)
ment and multiplication
4:d(a,in1R)
• A non-cooperative rule
a
a
n
1:aca is actually never
1L
1R ab
applied; used to stop the computation.
• n! are generated in n+1 step.
s
Yet faster growth
• Polymorphic, no targets: exponential of
polynomial
• Polymorphic, targets: exponential of
exponential.
• Upper bound
– The fastest growth is by squaring
– Having n+n+1 objects, in one step we can
obtain at most n2+n+1 objects.
Lower bound: Superpowers
,,2,,,4,,,16,,,256,,,65536,,,4294967296,,,18446744073709551616,,, …
• {2^(2n)|n0}NOP15(polym-d(ncoo),tar)
iterated squaring
5:ba’b’
2:aa
4:b 6:a’a
2(a,s)(b,1R)
(b,s)⇒
3:ac
7:b’(b,in1R) k
a ⇒(1:abk) bkk
a

rule
4:
cleanup
bb
1L
1R
s
• Stopped by rule 3 making 1:cbk.
• Numbers 2^(2n) generated in 3n+2 steps.
• No cooperation! Reminder: 15 membranes.
Deterministic computing
• ( n2^(2n) )DfOP15(polym+d(coo),tar)
• Similar to the previous system
– a in 1L powers one squaring
– Input dn in skin
– cd ⇒3 ca in 1L
Deterministic computing: remarks
• Disabling rules may be avoided: +d  -d
–
–
–
–
–
a‘s appear in skin every 3rd step
No need to disable rule 1 in the process of computing
Deterministic subtraction and appearance checking
c moves into 1L and blocks rule 1
n2^(2n) computed in O(n)
Deterministic deciding
• {n!|n1}NdDOP37(polym-d(coo),tar)
• Deciding is more than accepting
• Iterated division of the input number
– 4-step cycles
– Verifying quotient and remainder
• A number kn! is decided in at most 4n steps
(sublogarithmic w.r.t. k)
Summary - 1
• Polymorphic P systems as a variant of object
rewriting model of P systems: rules are
– Not specified explicitly (only features e.g. targets are)
– Dynamically inferred from the contents of inner
regions
• Idea: similar with cell nucleus, but simpler
• Conventional computing: von Neumann
architecture VS Harvard architecture
• Usual P systems cannot grow with factorial
speed; polymorphic P systems can
deterministically decide factorials of n in O(n)
• Nice possibilities like constant-time
multiplication/division
• Extensions possible
Summary - 2
•
•
•
•
•
Strong universality in OP47(polym-d(coo))
Superexp. growth in DOP7(polym-d(ncoo))
Gen. {n!nk}, n+k+1steps, OP13(polym-d(ncoo),tar)
Gen. n! in n+1steps, OP9(polym-d(coo),tar)
Generating 2^(2n) in 3n+2 steps by a P system
in OP15(polym-d(coo),tar)
• Computing n2^(2n) in O(n) steps by a P
system in DOP*(polym-d(coo),tar)
• Deciding factorials in sublogarithmic time by a P
system in DOP37(polym-d(coo),tar)
• Growth
Summary - 3
– polymorphic with targets (exp of exp) >
– polymorphic without targets (exp of poly) >
– non-polymorphic (exp)
• There exists infinite sets of numbers that are accepted in
time which is sublinear w.r.t. the size of the input in
binary representation (without cheating by only
examining a part of the input).
• Selected open questions
– Characterization of restricted classes
like OP*(polym-d(ncoo),ntar)
– “Real” applications for which non-polymorphic P systems are not
suitable
– Can polymorphic P systems use superexponential growth to
attack intractable problems in polytime? (Conjecture: no)
On
one
slide
(polym (coo))
•
•
•
•
•
Strong universality in OP47
-d
Superexp. growth in DOP7(polym-d(ncoo))
Gen. {n!nk}, n+k+1steps, OP13(polym-d(ncoo),tar)
Gen. n! in n+1steps, OP9(polym-d(coo),tar)
Generating 2^(2n) in 3n+2 steps by a P system
a85
in OP15(polym-d(ncoo),tar)
aa 1L a 1R
128
a
2L b 2R s
• Computing n2^(2n) in O(n)
⇒8
steps by a P system in
aa 1L a 1R
b4
a
DOP*(polym-d(coo),tar)
2L b 2R s
• Deciding factorials in sublogarithmic time by a P
system in DOP37(polym-d(coo),tar)
Thank you
for your questions