F on ie s o Memb ane Compu ing:
Open P oblems and Resea ch Topics
Ma ian Gheo ghe1, Gheo ghe P˘aun2,3,
Ma io J. P´e ez-Jim´enez3– Edi o s
1Depa men o Compu e Science, Uni e si y o Sheffield
Regen Cou , Po obello S ee , Sheffield S1 4DP, UK
[email p o ec ed]
2Ins i u e o Ma hema ics o he Romanian Academy
PO Box 1-764, 014700 Bucu e¸s i, Romania
3Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa
A da. Reina Me cedes s/n, 41012 Se illa, Spain
[email p o ec ed], [email p o ec ed]
Summa y. This is a lis o open p oblems and esea ch opics collec ed a e he Twel h
Con e ence on Memb ane Compu ing, CMC 2012 (Fon ainebleau, F ance (23 - 26 Au-
gus 2011), mean ini ially o be a wo king ma e ial o Ten h B ains o ming Week on
Memb ane Compu ing, Se illa, Spain (Janua y 30 - Feb ua y 3, 2012). The esul was
ci cula ed in se e al e sions be o e he b ains o ming and hen modified acco ding o
he discussions held in Se illa and acco ding o he p og esses made du ing he mee ing.
In he p esen o m, he lis gi es an image abou key esea ch di ec ions cu en ly ac i e
in memb ane compu ing.
In oduc ion
The idea o compiling a collec ion o open p oblems and esea ch opics in mem-
b ane compu ing (MC) occu ed du ing he Twel h In e na ional Con e ence on
Memb ane Compu ing, CMC 12, held in Fon ainebleau, Pa is, F ance, om 23 o
26 o Augus , 2011 (see h p://cmc12.lacl. /). The in i a ion o con ibu e
o such a collec ion was o mula ed du ing CMC 12 (and a e ha ein o ced by
email) and se e al esea che s answe ed his call. The esul was ci cula ed unde
he name o “mega-pape ” (mega because i has much mo e co-au ho s han any
o he pape in MC...), mean o be a wo king ma e ial o he Ten h B ains o m-
ing Week on Memb ane Compu ing, Se illa, Spain, Janua y 30 - Feb ua y 3, 2012
(BWMC 10). Du ing CMC 12 he e we e also discussions and sugges ions ega ding
some o he opics which a e no de eloped he e; o his eason we b iefly men ion
172 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
(some o ) hem: explo ing mo e sys ema ically hype compu a ion esea ch ideas
wi hin MC a ea; ocussing on ansla ions be ween diffe en classes o memb ane
sys ems (P sys ems) and s udying complexi y aspec s ela ed o hese ansla ions
( he goal being o impo esul s om a b anch o MC o ano he one); iden i ying
he mos “na u al” applica ions o P sys ems in modeling biological p ocesses and
p oducing a se o cohe en and con incing case s udies (a esea ch olume on
such applica ions in biology is now in p og ess); in es iga e in mo e de ails he dP
au oma a, hei efficiency and connec ions wi h communica ion complexi y; look
o biological applica ions o spiking neu al P sys ems.
Be o e p esen ing an o e iew o he pape we men ion [7], [8] as key e e ences
o gene al MC opics. Mo e specific MC opics, like MC and p ocess calculi [1],
in e play be ween MC and DNA compu ing [6] and con o mon MC sys ems [3],
a e also well-es ablished. Applica ions o MC in a ious a eas can be ound in [2].
The ini ial “mega-pape ” was changed se e al imes, inco po a ing discussions
and p og esses ca ied ou du ing BWMC 10. The p esen e sion is conside ed
a “closed” one (al hough such a p ojec can ne e be closed); o u he esul s
ela ed o he p oblems collec ed he e he eade is in i ed o ollow he MC websi e
om [9]. In pa icula , one can find he e he p oceedings olumes, wi h all pape s
eme ged in connec ion wi h he b ains o ming.
The ex s ecei ed om he con ibu o s we e e ised by hei au ho s a e
BWMC 10, and appea below in he final o m hey ha e been submi ed, wi h
minimal edi o ial changes. In mos cases, one gi es he necessa y (minimal) defi-
ni ions, as well as he ele an bibliog aphy. O cou se, he eade is supposed o
be amilia wi h basic elemen s o MC – o ins ance, om he sou ces men ioned
a he end o his in oduc ion. A quick in oduc ion o MC is gi en a he begin-
ning o his pape , jus o help he eade no amilia wi h his esea ch a ea o
ha e a fla o o i . A he beginning o each sec ion he e a e men ioned he main
no ions, om MC and om compu abili y in gene al, supposed o be known in
o de o unde s and he p oblems which ollow (some imes, pa o hese no ions
a e b iefly in oduced oge he wi h he p oblems). The au ho s o each “sec ion”
a e men ioned, wi h affilia ions and email add esses, so ha he in e es ed eade
can con ac hem o u he de ails, cla ifica ions and coope a ion in sol ing he
p oblems.
The o de in which he p oblems a e gi en below goes, app oxima ely, om gen-
e al issues o heo y and hen o applica ions. In wha conce ns he compu abili y
opics, he e a e sec ions de o ed o bo h powe and efficiency o P sys ems, con-
side ing hem as numbe s o s ings gene a o s o accep o s, in “old” e sions
(sympo /an ipo , ca aly ic, spiking neu al P sys ems) o in ecen ly in oduced
o ms (polymo phic, dP sys ems), looking o gene aliza ions (e.g., o “ke nel P
sys ems”) o o classic no ions o language heo y no ye ex ended o MC (such
as con ol wo ds); compu a ional complexi y is a i id di ec ion o in es iga ion,
add essing bo h ime and space complexi y (defining specific complexi y classes,
compa ing hem wi h exis ing classes, looking o possibili ies o sol ing compu a-
ionally ha d p oblems ( ypically, NP-comple e p oblems) in a polynomial ime,
F on ie s o Memb ane Compu ing 173
by making use o he massi e pa allelism o P sys ems and ading-off space o
ime, wi h he space ob ained by means o biologically inspi ed ope a ions, such as
memb ane di ision and memb ane c ea ion). The e m “ ype compu ing” ( ollow-
ing he model o “hype compu ing” = “passing beyond he Tu ing ba ie ”, wi h
he ini ial “ ” coming om “ as ”) ies o call a en ion o a sys ema ic s udy
o “passing polynomially beyond he NP ba ie ”. All classes o P sys ems a e
conside ed: cell-like, issue-like, (spiking) neu al, and nume ical. Mo ing o appli-
ca ions, one men ions issues ela ed o he seman ics, o mal e ifica ion, possible
b idges wi h eac ion sys ems (a younge “sis e ” esea ch a ea o na u al compu -
ing, inspi ed om biochemis y). The applica ions e e bo h o he simula ion o
biological and bio-medical p ocesses and o (somewha unexpec ed) applica ions
in app oxima e op imiza ion (basically, dis ibu ed e olu iona y algo i hms, wi h
he dis ibu ion con olled by means o memb anes, and bo owing ing edien s
om MC), obo ics (mobile obo s con olled by means o nume ical P sys ems),
and compu e g aphics, as well as o mo e specula i e ideas, dealing, o ins ance,
wi h he unc ioning o he b ain.
The na u e o ques ions ange om local/ echnical open p oblems, asking o
imp o e exis ing esul s, especially o a be e delimi a ion o he bo de line be-
ween uni e sali y and non-uni e sali y, be ween efficiency and non-efficiency (in
pa icula , conce ning he influence o some quali a i e pa ame e s, such as he
numbe o memb anes, he size o he ules, o quali a i e ea u es, such as he di -
e ence be ween de e minis ic and non-de e minis ic sys ems, using o no a ious
ypes o ules), o “s a egic” issues, o ins ance, ela ing MC wi h o he esea ch
a eas, such as compu e science, biology, ecology, obo ics and so on. O cou se,
many o he p ecise p oblems o esea ch ideas ci cula e wi hin he MC communi y
(o can be ound in ecen pape s; see also he p e ious b ains o ming olumes,
whe e many p oblems a e o mula ed, some imes gi en in explici lis s; he “ a e”
o some o hese open p oblems is ecalled in he pape Gh. P˘aun, “T acing Some
Open P oblems in Memb ane Compu ing”, Romanian J. o In o ma ion Science
and Technology, 10, 4 (2007), 303–314). Simila ly, some o he p oblems p oposed
in he p esen pape o a ian s o hem we e al eady ci cula ed wi hin he MC
communi y also be o e, a ac which should call a en ion o hem (as an indica ion
o bo h in e es and difficul y).
We a e awa e, on he one hand, ha many o he au ho s, who ha e no an-
swe ed ou eques (in ime), would ha e o he p oblems o p opose, and, on he
o he hand, ha many people keep o hem, o hei immedia e esea ch, he
“juicy” opics... Anyway, we hope ha his collec ion will bo h aise he in e -
es o he eade in app oaching MC and, maybe, in pa icipa ing in he u u e
edi ions o he yea ly BWMC.
Because se e al sec ions below e e o he CMC 12 p e-p oceedings and p o-
ceedings olumes, we also men ion hem below – [4] and [5], espec i ely.
174 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
Re e ences
1. G. Ciobanu: Memb ane Compu ing. Biologically Inspi ed P ocess Calculi. The Pub-
lishing House o he “Al.I. Cuza” Uni e si y, Ia¸si, 2010.
2. G. Ciobanu, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.: Applica ions o Memb ane Compu -
ing. Sp inge , Be lin, 2006.
3. P. F isco: Compu ing wi h Cells. Ad ances in Memb ane Compu ing. Ox o d Uni .
P ess, 2009.
4. M. Gheo ghe, Gh. P˘aun, S. Ve lan, eds.: Twel h In e na ional Con e ence on Mem-
b ane Compu ing, CMC12, Fon ainebleau, F ance, 23–26 Augus 2011. LACL, Uni .
Pa is Es – C ´e eil Val de Ma ne, 2011.
5. M. Gheo ghe, Gh. P˘aun, G. Rozenbe g, A. Salomaa, S. Ve lan, eds.: Memb ane Com-
pu ing. 12 h In e na ional Con e ence, CMC 2011, Fon ainebleau, F ance, Augus
2011, Re ised Selec ed Pape s, LNCS 7184, Sp inge , Be in, 2012.
6. A. P˘aun: Compu abili y o he DNA and Cells. Splicing and Memb ane Compu ing.
SBEB Publishing, Choud an , Louisiana, USA, 2008.
7. Gh. P˘aun: Memb ane Compu ing. An In oduc ion. Sp inge , Be lin, 2002 (Chinese
ansla ion in 2012).
8. Gh. P˘aun, G. Rozenbe g, A. Salomaa, eds.: The Ox o d Handbook o Memb ane Com-
pu ing. Ox o d Uni . P ess, 2010.
9. The P Sys ems Websi e: www.ppage.psys ems.eu.
Con en s
1. A Glimpse o Memb ane Compu ing (The Edi o s)
2. Some Gene al Issues (J. Beal)
3. The Powe o Small Numbe s (A. Alhazo )
4. Polymo phic P Sys ems (S. I ano , A. Alhazo , Y. Rogozhin)
5. P Colonies and dP Au oma a (E. Csuhaj-Va j´u)
6. Spiking Neu al P Sys ems (L. Pan, T. Song)
7. Con ol Wo ds Associa ed wi h P Sys ems (K. K i hi asan, Gh. P˘aun, A.
Ramanujan)
8. Speeding Up P Au oma a (G. Vaszil)
9. Space Complexi y and he Powe o Elemen a y Memb ane Di ision (A. Lep-
o a i, G. Mau i, A.E. Po eca, C. Zand on)
10. The P-Conjec u e and Hie a chies (N. Mu phy)
11. Seeking Sha pe F on ie s o Efficiency in Tissue P Sys ems (M.J. P´e ez-
Jim´enez, A. Riscos-N´u˜nez, M. Rius-Fon , ´
A. Rome o-Jim´enez)
12. Time-F ee Solu ions o Ha d Compu a ional P oblems (M. Ca alie e)
13. Fype compu a ions (Gh. P˘aun)
14. Nume ical P Sys ems (C. Vasile, A.B. Pa el, I. Dumi ache, Gh. P˘aun)
15. P Sys ems Fo mal Ve ifica ion and Tes ing (F. Ipa e, M. Gheo ghe)
16. Causali y, Seman ics, Beha io (O. Ag igo oaiei, B. Aman, G. Ciobanu)
F on ie s o Memb ane Compu ing 175
17. Ke nel P Sys ems (M. Gheo ghe)
18. B idging P and R (Gh. P˘aun)
19. P Sys ems and E olu iona y Compu ing In e ac ions (G. Zhang)
20. Me abolic P Sys ems (V. Manca)
21. Un a eling Oscilla ing S uc u es by Means o P Sys ems (T. Hinze)
22. Simula ing Cells Using P Sys ems (A. P˘aun)
23. P Sys ems o Compu a ional Sys ems and Syn he ic Biology (M. Gheo ghe,
V. Manca, F.J. Rome o-Campe o)
24. Biologically Plausible Applica ions o Spiking Neu al P Sys ems o an Expla-
na ion o B ain Cogni i e Func ions (A. Ob ulowicz)
25. Compu e Vision (D. D´ıaz-Pe nil, M.A. Gu i´e ez-Na anjo)
26. Open P oblems on Simula ion o Memb ane Compu ing Models (M. Ga c´ıa-
Quismondo, L.F. Mac´ıas-Ramos. M.A. Ma ´ınez-del-Amo , I. P´e ez-Hu ado,
L. Valencia-Cab e a)
1 A Glimpse o Memb ane Compu ing
Memb ane compu ing (MC) is a b anch o na u al compu ing (in oduced in [1],
wi h he epo e sion o he pape ci cula ed as Tu ku Cen e o Compu e
Science – TUCS Repo 208, in No embe 1998, see www. ucs. i) which aims o
abs ac compu ing models om he s uc u e and he unc ioning o he li ing
cell and om popula ions o cells (e.g., issues, o gans), including he b ain. One
o he basic no ions is ha o a memb ane, unde s ood as a 3D esicle, sepa a ing
“an inside” and “an ou side”, whe e objec s can be placed and whe e specific bio-
chemis ies ake place. The memb anes can be a anged in a hie a chical s uc u e
(like in a cell, hence desc ibed by a ee) o in an a bi a y s uc u e (like in issues,
hence desc ibed by a g aph). The space be ween a memb ane and he memb anes
placed immedia ely inside i (pa en -child en, in a ee) is called egion o com-
pa men . A memb ane wi hou any memb ane inside is said o be elemen a y. In
he case o a cell-like a angemen o memb anes, he ex e nal memb ane is called
he skin. The space ou side he skin memb ane is called he en i onmen (and
simila ly is called he space ex e nal o all memb anes o a issue-like memb ane
s uc u e). A memb ane s uc u e can be o mally ep esen ed by a oo ed labeled
ee (each memb ane is iden ified by a label, which is hen associa ed wi h he node
o he ee associa ed wi h he memb ane), o , co espondingly, by an exp ession
o labeled pa en heses, wi h a unique ex e nal pai o pa en heses, co esponding
o he skin memb ane.
The objec s a e p esen in he egions o a memb ane s uc u e and in he en i-
onmen in he o m o mul ise s, se s wi h hei elemen s p esen in a gi en numbe
o copies (se s wi h mul iplici ies o elemen s). The mul iplici y can be fini e (ex-
p essed by a na u al numbe ) o infini e/a bi a y (we say ha an objec wi h his

176 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
p ope y is o ωmul iplici y). Fo he beginning, le us ha e in mind only a omic
objec s, ep esen ed by symbols o a gi en (fini e) alphabe , and le us imagine
ha hey co espond o he chemical compounds, om ions o mac omolecules,
which swim in wa e in he cell compa men s. In his amewo k, i is con enien
o ep esen he mul ise s by s ings o symbols, wi h he numbe o occu ences o
a symbol in a s ing co esponding o he mul iplici y o ha objec in he mul ise
( ha is, any pe mu a ion o a s ing ep esen s he same mul ise ). These objec s
eac , acco ding o gi en e olu ion ules. The basic ones (o en simply called “e o-
lu ion ules”) a e he mul ise ew i ing ules co esponding o he biochemical
eac ions aking place in a cell. They a e o he o m u→ , whe e uand a e
mul ise s. Many o he ypes o e olu ion ules a e inspi ed by o he biological op-
e a ions. We men ion he e only he basic ones: sympo /an ipo co espond o
he coupled passage o chemicals h ough ( he p o ein channels embedded in) he
cell memb anes, memb ane di ision co esponds o mi osis, memb ane c ea ion
and memb ane dissolu ion can also be associa ed wi h biological p ocesses ( he
same wi h exo- and endocy osis, bu we do no en e in o de ails). The e also a e
mo e complex ypes o ules, o ules inspi ed om compu e science (b oadcas -
ing, communica ion be ween wo memb anes placed in a common en i onmen ),
ules mimicking he way he neu ons communica e by means o spikes (elec ical
impulses o iden ical shapes). Impo an is ha bo h he ules and he objec s a e
placed in compa men s and ha he ules ac locally, on he objec s in he same
compa men . Objec s can also pass h ough memb anes, bo h in he cell-like case
and in he issue-like case, hence he compa men s coope a e.
The e a e se e al ways he ules a e applied (se e al seman ics). The mos
in es iga ed one, co esponding o he pa allelism o eac ions in a solu ion, is
he maximal pa allelism: a maximal mul ise o ules is used, whe e maximali y is
defined in he sense o mul ise inclusion (no ules can be added o he mul ise
so ha he ob ained mul ise o ules is s ill applicable o he mul ise o objec s
p esen in he espec i e compa men ). When se e al (maximal) mul ise s can
be applied, he one o use is chosen nonde e minis ically. Many o he possibili ies
we e conside ed: sequen ial, limi ed pa allelism, minimal pa allelism ( he idea is
ha each compa men which can use a ule – hence i is “ali e” – has o use a
leas one ule, wi h na u al ex ensions o P sys ems whose ules a e no associa ed
wi h compa men s – as i is he case o sympo /an ipo sys ems, whe e he ules
a e associa ed wi h he memb anes). In all hese cases, he sys em is synch onized,
a uni e sal clock exis s which measu es he ime in he same way o all memb anes
and wi h ules used, synch onously, in each ime uni . The na u al coun e pa is
ha o asynch onous sys ems.
Such a de ice, consis ing o memb anes, objec s, e olu ion ules, is called a
memb ane sys em – cu en ly called also a P sys em.
S a ing om an ini ial configu a ion (memb anes and objec s) o a P sys em
and using he ules acco ding o a chosen s a egy, one ob ains compu a ions,
sequences o ansi ions among configu a ions. I a configu a ion is ob ained such
ha no ule can be applied, we say ha he sys em hal s. Se e al esul s can be
F on ie s o Memb ane Compu ing 177
associa ed wi h a hal ing compu a ion, o ins ance, in he o m o he numbe o
objec s p esen in he hal ing configu a ion in a designa ed elemen a y memb ane.
A P sys em can hen be seen as a gene a i e de ice, gene a ing a se o numbe s:
because o nonde e minism, we ha e se e al compu a ions, hence se e al numbe s.
Fo mally, a P sys em o he basic o m (cell-like, wi h symbol objec s, e ol ing
by mul ise ew i ing ules) can be gi en as ollows ( o an alphabe A, we deno e
by A∗ he se o all s ings o e A, including he emp y s ing λ;A∗− {λ}is
deno ed by A+):
Π= (O, µ, w1, . . . , wm, R1, . . . , Rm, i0),whe e
mis he deg ee o he sys em,
Ois he alphabe o objec s,
µis he memb ane s uc u e, wi h mmemb anes,
w1, . . . , wm∈O∗a e mul ise s associa ed wi h he m egions o µ,
R1, . . . , Rma e fini e ules o he o m u→ whe e uand a e
mul ise s o e Owi h he objec s in also ha ing a ge indica ions
o he o m in, ou , he e; an objec wi h indica ion ou exi s
he memb ane, one wi h he indica ion he e emains in he same egion,
and one wi h he a ge in en e s any o he memb anes delimi ing
he egion om below, nonde e minis ically choosing he des ina ion,
i0is he label o he ou pu memb ane, he one whe e he esul is ob ained.
A ansi ion be ween wo configu a ions C1, C2o Πis deno ed by C1=⇒C2, and
he se o numbe s gene a ed by Πis deno ed by N(Π).
The ules o he a bi a y o m u→ a e said o be coope a i e, i u∈O,
hen he ule is called non-coope a i e (i co esponds o con ex - ee ules in a
g amma ); an in e media e case is ha o ca aly ic ules, which a e o he o m
ca →c , whe e c∈Ois a ca alys , assis ing he objec a∈O o ge ans o med
in o ∈O∗. When applying a ule u→ , he objec s om ua e consumed and
hose om a e p oduced.
An an ipo ule is o he o m (u, ou ; , in) wi h u, ∈O∗; using such a ule
(associa ed wi h a memb ane i) means o mo e he mul ise uou side memb ane
i, simul aneously wi h b inging he mul ise inside he memb ane. I one o he
mul ise s u, is emp y, hen he ule becomes a sympo one.
We do no gi e he e u he echnical defini ions o no a ions; he in e es ed
eade can consul any o he i les indica ed in he end o he In oduc ion, espe-
cially he Handbook [8].
Howe e , we men ion in o mally a se ies o no ions and o u he classes o P
sys ems. The e a e many possibili ies o ex end he p e iously in oduced com-
pu ing de ice and i s unc ioning. Ins ead o coun ing objec s in a compa men ,
we can conside as he esul o a compu a ion he sequence o objec s sen o he
en i onmen ( his is he so-called, ex e nal ou pu ), hence a P sys em can hen
178 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
gene a e a language. A language is ob ained also i we ollow he ace o a special
objec s ac oss memb anes. Then, we can use a (sympo /an ipo ) P sys em in
he accep ing mode: he objec s en e ing he sys em om he en i onmen a e
a anged in a s ing and we say ha he s ing is accep ed i he compu a ion
hal s. In he case o issue P sys ems, he objec s can e ol e inside memb anes
by mul ise ew i ing ules and can pass om a memb ane o ano he one by an-
ipo ules. The communica ion channels among memb anes a e hence implici ly
defined by he p o ided ules o communica ion; a mo e complex case is ha o
popula ion P sys ems, whe e he e also a e ules o es ablishing channels be ween
cells and o des oying hem. Besides ules o handling objec s, we can also ha e
ules o changing he memb ane s uc u e. We men ioned di ision, c ea ion, and
dissolu ion ules, exo- and endocy osis, bu he e also a e sepa a ion, budding,
gemma ion ules. Obse e he biological inspi a ion, al hough abs ac ed in a way
which b ings us a om biology – in hei ini ial o ms, P sys ems we e no mean
o be used as models wi h a biological ele ance. The objec s can be desc ibed by
symbols, as abo e, bu hey can also ha e a s uc u e, o ins ance, desc ibed by
s ings (p ocessed by s ing ope a ions, such as ew i ing, DNA splicing, eplica-
ion, inse ion-dele ion), o e en mo e complex, such as 2D a ays, ees, e c. A
special case is ha o nume ical P sys ems, whe e nume ical a iables a e placed
in he egions o a cell-like memb ane s uc u e, e ol ing by means o p og ams,
composed o a p oduc ion unc ion (e.g., a polynomial), and a epa i ion p o o-
col; in each compa men , he local a iables a e subjec o a local p oduc ion
unc ion, and he alue o his unc ion is dis ibu ed among he a iables in ha
egion and in he neighbo ing egions acco ding o he epa i ion p o ocol (e.g.,
p opo ionally wi h gi en numbe s, pa o he p og am). The model, somewha
inspi ed om economics, can bo h gene a e se s o numbe s, bu also compu e
unc ions o se e al a iables, a si ua ion which is comple ely diffe en om he
gene a i e-accep ing unc ioning o usual objec -based P sys ems. An in e es ing
a ian is ha o P sys ems wi h objec s bound on memb anes (as ac ually is he
case wi h many chemicals in a cell), and hen wi h he ules e ol ing a he same
ime objec s which a e ee inside egions and hese fixed objec s.
Finally, le us men ion he so-called spiking neu al P sys ems (SN P sys ems),
whe e memb anes ( ep esen ing neu ons) a e placed in he nodes o a g aph, whose
links ep esen synapses, holding se e al copies o a single objec , co esponding
o a spike; he spikes e ol e by ules which fi s check he con en s o he neu on
(by means o a egula exp ession), consume a numbe o spikes and p oduce a
numbe o spikes, which a e sen , immedia ely o wi h a delay, o all neu ons o
which a synapse goes om he neu on whe e he ule was used. The spikes sen o
he en i onmen by a designa ed ou pu neu on o m he spike ain p oduced by
he sys em; numbe s o s ings can be associa ed wi h a spike ain, hence again
a gene a i e de ice is ob ained.
Up o now, we men ioned only he gene a i e mode (co esponding o g am-
ma s) o using a P sys em. A dual case (co esponding o au oma a) is he ac-
cep ing mode: a numbe is in oduced in a sys em, e.g., as he mul iplici y o a
F on ie s o Memb ane Compu ing 179
specified objec in a specified compa men , and he numbe is accep ed i he
compu a ion hal s. S ings can also be ecognized, by b inging hei symbols, one
by one, in a sys em (e.g., in a sympo /an ipo one), wi h he s ing accep ed i
he compu a ion hal s.
In all cases, we can also use a P sys em as a decidabili y machine: a decision
p oblem (wi h YES/NO answe ) is in oduced in he sys em, encoded in a specified
way in he o m o a mul ise , and he sys em says whe he he p oblem (ac ually,
i s ins ance in oduced in he ini ial configu a ion) has an affi ma i e answe by
hal ing o by sending a special objec yes in o he en i onmen . This is he usual
way o in es iga ing he compu a ional complexi y o P sys ems ( he ime o he
space needed o sol e a class o decidabili y p oblems).
Mos classes o P sys ems a e compu a ionally comple e, equi alen wi h Tu ing
machines (one also says ha hey a e uni e sal), e en in es ic ed cases: small
numbe o memb anes, using only ca aly ic ules (wi h a leas wo ca alys s: he
powe o one ca alys P sys ems is s ill open), sympo /an ipo ules o educed
sizes, SN P sys ems o es ic ed o ms, e c. Simila ly, many classes o P sys ems
able o c ea e an exponen ial wo king space in a linea ime ( he ypical case is ha
o P sys ems using memb ane di ision, also called wi h ac i e memb anes) can sol e
NP-comple e p oblems (some imes e en PSPACE p oblems) in a polynomial
ime. The li e a u e o MC abounds in esul s o hese ypes.
An impo an pa o he esea ch in MC deals wi h applica ions. Using P sys-
ems o modeling p ocesses aking place in a cell o in complexes o cells, such as
popula ions o bac e ia, is expec ed; he model s a s om biology, hence i is na u-
al o e u n o biology. Se e al ea u es make P sys ems a ac i e o he biologis
(especially in compa ison wi h he models based on diffe en ial equa ions): he di-
ec connec ion wi h he biochemis y, which also means a high unde s andabili y,
he mul icompa men al s uc u e, he easy scalabili y, he in insic disc e e na-
u e o he model, he easy p og ammabili y, he possibili y o a ach p obabili ies
( eac ion a es, s oichiome ic coefficien s) o he e olu ion ules, he eme gen
beha io o a P sys em ( he o e all e olu ion is no a all a “sum” o he pa s
e olu ion). All hese applica ions a e based on simula ion p og ams ( he e a e se -
e al such p og ams a ailable – see he webpage o he domain, men ioned in he
bibliog aphy o he In oduc ion, [9]). Mos o hem un on he usual sequen ial
compu e s, bu he e also a e a emp o implemen P sys ems on dedica ed ha d-
wa e, clus e s and g ids, on pa allel ha dwa e (such as NVIDIA g aphical ca ds).
A specialized p og amming language, P-lingua, was also elabo a ed.
Also somewha expec ed a e he applica ions in modeling and simula ing eco-
sys ems (we ha e “memb anes” whe e se e al agen s in e ac , like he chemicals in
a cell). No so expec ed howe e a e he applica ions in app oxima e op imiza ion
(dis ibu ed e olu iona y compu ing), compu e g aphics ( ollowing he s yle o L
sys ems based g aphics, bu also ecen a emp s o p ocess images in he pa allel
amewo k o P sys ems), while he ecen applica ions o nume ical P sys ems in
con olling mobile obo s is comple ely unexpec ed.
186 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
iR o all 1 ≤i≤m. The s ing wh,h∈H, is he ini ial con en o he memb ane
wi h label h. The label iou indica es he egion whe e he ou pu o he sys em
will be ead om. We will desc ibe he mapping φla e on.
Obse e ha he desc ip ion o he sys em does no include any ule. Ins ead,
he con en s o he memb anes wi h labels iL and iR a e in e p e ed as he le -
hand side and igh -hand side o he ule i espec i ely. A e e y s ep, he ules a e
applied in he usual way. As a esul o applica ion o he ule i, he igh -hand side
o he ule ( he con en o iR) is injec ed in o φ(i). The la e mapping is defined as
ollows: φ:{1, . . . , m} → Ta ,Ta ={inj|j∈His an inne memb ane o p} ∪
{ou , he e}, whe e p∈His he label o he memb ane con aining he ule i( he
memb anes iL and iR). Fo u he in o ma ion we e e he eade o [1].
Polymo phic P sys ems ha e no ye been explo ed sufficien ly well. In he
ollowing pa ag aphs we lis some open p oblems which we find o in e es .
•Sol e ha d p oblems. I has been shown ha polymo phic P sys ems can sol e
ce ain p oblems as e han any o he P sys em model ( o example, hey
gene a e n2in O(1) and gene a e 22nin O(n)). So a , only ela i ely simple
p oblems we e conside ed, bu we belie e ha he polymo phic model has he
po en ial o acili a e sol ing much ha de p oblems. Fo example, possibili ies
o find he G ¨obne basis using polymo phic P sys ems a e cu en ly being
conside ed.
•Cha ac e ize p oblems which may be sol ed as e . A mo e gene al ques ion, on
he o he hand, is o define he class o p oblems which can be sol ed mo e
efficien ly using polymo phic P sys ems. I has been obse ed ha , o mul-
iplica ion, linea speed-up was in oduced; a much mo e sys ema ic esea ch
in his di ec ion is necessa y. In pa icula , i is unclea whe he i is possi-
ble o use he polymo phism o cons uc exponen ial wo kspace o sol ing
in ac able p oblems in polynomial ime.
•Polymo phic P sys ems wi h ac i e memb anes. Polymo phic P sys ems a e
a ai ly simple model a he momen . This means, in pa icula , ha ce ain
ex ensions a e possible. We would like o pa icula ly s ess he pe spec i es o
conside ing polymo phic P sys ems wi h ac i e memb anes, whe e he mem-
b ane s uc u e i sel does no s ay cons an . Such a combina ion is a e y
powe ul one, he e o e i is impo an o es ablish some es ic ions which will
define an as simple as possible, ye sufficien ly powe ul, cons uc .
•The powe o he mos es ic ed a ian . Ano he way o explo e polymo phic
P sys ems is cha ac e izing he powe o models wi h he minimal numbe o
addi ional ing edien s (non-coope a i e ules, no ules wi h emp y le -hand
side, no a ge indica ions). In [1] i is shown ha e en his model can easily
achie e supe exponen ial g ow h; i is impo an o know how powe ul poly-
mo phism on i s own is.
•Sel -assembly. Finally, we make he obse a ion ha ules in polymo phic P
sys ems may be ea ed as esul s o in e ac ion o couples o ini ially indepen-

F on ie s o Memb ane Compu ing 187
den memb anes, which ha e gained addi ional capabili ies by connec ing o
each o he . The whole polymo phic P sys em may be ea ed as a s age in he
p ocess o in e ac ion o memb anes in a sys em o memb anes. This b ings
abou , in pa icula , he ques ion o sel -assembly o memb ane s uc u es.
Re e ences
1. A. Alhazo , S. I ano , Yu. Rogozhin: Polymo phic P sys ems. 11 h In e na ional Con-
e ence on Memb ane Compu ing (M. Gheo ghe e al., eds.), CMC 2010, Jena, Ge -
many, LNCS 6501, Sp inge , Be lin, 2010, 81–94.
5 P Colonies and dP Au oma a
E zs´ebe Csuhaj-Va j´u
Depa men o Algo i hms and Thei Applica ions
Facul y o In o ma ics, E¨o ¨os Lo ´and Uni e si y, Budapes , Hunga y
[email p o ec ed]
Requi ed No ions: issue-like P sys em, P colony, dP au oma on
5.1 P Colonies
P colonies a e a ian s o e y simple issue-like P sys ems, modeling a communi y
o e y simple cells li ing oge he in a sha ed en i onmen ( o basic in o ma ion
see [8]).
In he basic model, he cells (o agen s) a e ep esen ed by a collec ion o
objec s and ules o p ocessing hese objec s. The agen s a e es ic ed in hei
capabili ies, i.e., only a limi ed numbe o objec s, say, kobjec s, a e allowed o
be inside any cell du ing he unc ioning o he sys em. Numbe kis said o be
he capaci y o he P colony. The ules o he cells a e ei he o he o m a→b,
speci ying ha an in e nal objec ais ans o med in o an in e nal objec b, o
o he o m c↔d, speci ying he ac ha an in e nal objec cis sen ou o
he cell, o he en i onmen , in exchange o he objec d, which is p esen in he
en i onmen . A e applying hese ules in pa allel, a cell con aining he objec s
a, c will con ain he objec s b, d. Wi h each cell, a se o p og ams composed o
such ules is associa ed. In he case o P colonies o capaci y k, each p og am has
k ules; he ules o he p og am mus be applied in pa allel o he objec s in he
cell.
The cells o a P colony execu e a compu a ion by synch onously applying hei
p og ams o objec s inside he cells and ou side in he en i onmen . A he be-
ginning o he compu a ion, pe o med by a gi en P colony o capaci y k, he
188 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
en i onmen con ains a bi a ily many copies o a dis inguished symbol e, called
he en i onmen al symbol (and no o he symbols); u he mo e, each cell con ains
kcopies o e. When a hal ing configu a ion is eached, ha is, when no mo e ules
can be applied, he esul o he compu a ion is ead as he numbe o ce ain
ypes o objec s p esen in he en i onmen .
P colonies ha e been ex ensi ely examined du ing he yea s. I was shown ha
hese simple cons uc s a e compu a ionally comple e compu ing de ices e en wi h
e y es ic ed size pa ame e s and wi h o he syn ac ical o unc ioning es ic-
ions. Se e al ex ensions o he model ha e al eady been in es iga ed as well: P
colonies wi h dynamically a ying en i onmen (eco-P colonies) [1] o PCol au-
oma a [2], cons uc s whe e he beha io o he cells is influenced by di ec im-
pulses coming om he en i onmen s ep-by-s ep. In he case o a PCol au oma on
a ape wi h an inpu s ing is gi en wi h he P colony, i.e., he model is augmen ed
wi h a s ing pu on an inpu ape o be p ocessed by he P colony.
Excep PCol au oma a, P colonies ha e been conside ed as gene a ing de ices,
bu he cons uc can also be conside ed as a (mul ise ) accep ing de ice (called
accep ing P colony o P colony accep o ), possibly wo king in an au oma on-like
ashion as well. In he ollowing we p opose p oblems and p oblem a eas in his
di ec ion.
To define such a model, suppose ha we ha e a P colony Πo capaci y kand
ini ialize he en i onmen wi h a gi en fini e mul ise o symbols Mwhe e each
symbol is diffe en om he en i onmen al symbol e. Le also conside an ini ial
configu a ion, i.e., le us dedica e an ini ial s a e o any cell and le us dis inguish
a se o accep ing configu a ions. Then, we say ha Mis accep ed by Π, i a e
pe o ming a fini e compu a ion (in some compu a ion mode) he en i onmen
consis s o only symbols e.
I is easy o see ha we may conside se e al a ian s o his model. Fo ex-
ample,
•we can limi he numbe o symbols in he en i onmen (no necessa ily wi h
a fini e cons an , bu wi h some unc ion o he size o he P colony) and
s udy he compu a ional powe o hese sys ems wi h limi ed wo kspace o
he compu a ion,
•we can conside he mul ise s in he en i onmen du ing he compu a ion as
pe mu a ions o wo ds (o map hem o wo ds in some o he way) being on
he inpu ape o an au oma a and s udy he ela ion o hese cons uc s and
classical au oma a;
•we can map he sequences o mul ise s o objec s en e ing each cell du ing he
compu a ion o wo ds being on he inpu ape o a mul i ape o mul ihead
au oma a and desc ibe he co espondence be ween hese cons uc s and he
classical mul i ape o mul ihead au oma a a ian s.
By in oducing double alphabe s as in he case o dP au oma a o desc ibing
wo-way mul ihead fini e au oma a ([3]), au oma a wi h wo-way mo ion o heads
can also be in e p e ed in he amewo k o accep ing P colonies.
F on ie s o Memb ane Compu ing 189
The concep o accep ing P colonies can be ex ended in some o he manne s
as well. Fo example, we do no fix he numbe o cells in he P colony in ad-
ance bu i is de e mined by he numbe o non-en i onmen al symbols in he
en i onmen a he beginning. Spa ial P colonies can also be defined. In his case
spa ial pa ame e s a e added o he cells and a neighbo hood ela ion among he
componen s is gi en; a cell can impo only such symbols om he en i onmen
which we e issued by i s neighbo s (a e placed in i s own en i onmen ).
Accep ing P colonies can be ela ed o cellula au oma a as well. One na u al
idea is o define P colonies co esponding o one-way cellula au oma a, which
a e linea a ays o iden ical copies o de e minis ic fini e au oma a, called cells,
wo king synch onously a disc e e ime s eps. Each cell is connec ed o i s imme-
dia e neighbo s o he igh . The cells a e iden ified by posi i e in ege s. The s a e
ansi ion depends on he cu en s a e o a cell i sel and he cu en s a e o i s
neighbo . An inpu wo d is accep ed by a one-way cellula au oma on i a some
s ep in he cou se o he compu a ion he le mos cell en e s an accep ing s a e.
A pa icula a ian o one-way cellula au oma a is he one whe e only a fixed
numbe , say k, cells a e gi en. This wo ks simila ly o he un es ic ed case, bu
he inpu is p ocessed in a diffe en manne , namely, he inpu is no gi en a he
beginning, bu i is p ocessed by he igh mos cell, symbol by symbol. Since he
neighbo hood can be defined in P colonies wi h emi ing special symbols (signals)
in he en i onmen and any cell in he P colony may ha e only a fini e numbe
o configu a ions (s a es), he eade may obse e ha he wo compu a ional
models, he accep ing P colony and he k-cell one-way cellula au oma on a e
s ongly ela ed.
Ob iously, mo e gene al cellula au oma a models can also be desc ibed by P
colony accep o s. Fo example, he abo e ex ension o he concep o P colonies
whe e he numbe o cells is de e mined by he numbe o ini ial non-en i onmen al
symbols can co espond o he un es ic ed case. We can also model d-dimensional
cellula au oma a (d≥1) by defining he neighbo hood ela ion be ween cells o
P colonies in an app op ia e manne . Cellula au oma a heo y has been a highly
elabo a ed field o na u e-mo i a ed, pa allel compu ing (see, o example, [5],
[6], [7]), hus by building b idges be ween P colony heo y and cellula au oma a
heo y, many in e es ing p oblems can also be s udied.
5.2 dP Au oma a
In addi ion o compa ing accep ing P colonies o a ian s o classical au oma a, we
may explo e he diffe ences and simila i ies be ween hese cons uc s and (fini e)
dP au oma a as well. A de ailed s udy in his di ec ion would also help in be e
unde s anding he na u e o hese wo cons uc s.
P au oma a a e a ian s o an ipo P sys ems accep ing s ings in an
au oma on-like ashion ( o a summa y on P au oma a, see Chap e 6 o [8]). The
no ion o a dis ibu ed P au oma on (dP au oma on in sho ) was in oduced in
[9]. Such a sys em consis s o a fini e numbe o componen P au oma a which ha e
190 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
hei sepa a e inpu s and which also may communica e wi h each o he by means
o special an ipo -like ules. A s ing accep ed by a dP au oma on is ob ained
in [9] as he conca ena ion o he s ings accep ed by he indi idual componen s
du ing a compu a ion pe o med by he sys em. A dP au oma on is called fini e
i i has only a fini e numbe o diffe en configu a ions.
The compu a ional powe o dP au oma a was s udied in [9], [4], [10], and
[11]. In [3] a connec ion be ween fini e dP au oma a and non-de e minis ic mul i-
head fini e au oma a was explo ed. I was shown ha he language o a non-
de e minis ic one-way mul i-head fini e au oma on and he language o a non-
de e minis ic wo-way mul i-head fini e au oma on can be ob ained as so-called
weak ag eemen language o s ong ag eemen language o a one-way, i.e., a usual
fini e dP au oma on, and a wo-way fini e dP au oma on.
The eade may easily obse e ha fini e dP au oma a, P colony accep o s and
cellula au oma a a e closely ela ed concep s. Thei compa a i e s udy would be
a p omising and e y use ul a ea in P sys ems heo y.
Acknowledgemen . Wo k suppo ed in pa by he Hunga ian Resea ch Fund
“OTKA”, p ojec K75952.
Re e ences
1. L. Cienciala, L. Ciencialo ´a: Eco-P colonies. P oc. WMC 2009, LNCS 5957 (Gh.
P˘aun e al., eds.), Sp inge , 201–209.
2. L. Ciencala, L. Ciencialo ´a, E. Csuhaj-Va j´u, Gy. Vaszil: PCol au oma a: Recognizing
s ings wi h P colonies. P oc. BWMC 2010, Se illa, 2010 (M.A. Ma ´ınez-del-Amo
e al., eds.), F´enix Edi o a, Se illa, 2010, 65–76.
3. E. Csuhaj-Va j´u, Gy. Vaszil: A connec ion be ween fini e dP au oma a and mul i-
head fini e au oma a. P oc. Twel h In e na ional Con e ence on Memb ane Com-
pu ing, Fon ainebleau, 23-26 Augus , 2011 (M. Gheo ghe e al., eds.), 109–126.
4. R. F eund, M. Kogle , Gh. P˘aun, M.J. P´e ez-Jim´enez: On he powe o P and dP
au oma a. Annals o Bucha es Uni . Ma h.-In o ma ics Se ies, 63, 2009, 5–22.
5. M. Ku ib: Na u e-based p oblems in cellula au oma a, P oc. CiE 2011, LNCS 6735,
Sp inge , 2011, 171–180.
6. M. Ku ib, J. Le e e, A. Malche : The size o one-way cellula au oma a. P oc.
Au oma a 2010: Disc e e Ma hema ics and Theo e ical Compu e Science, DMTCS,
2010, 71–90.
7. M. Holze , M. Ku ib: Cellula au oma a and he ques o non i ial a ificial
sel - ep oduc ion. P oc. Con . on Memb ane Compu ing, CMC 2010, LNCS 6501,
Sp inge , 2010, 19–36.
8. Gh. P˘aun, G. Rozenbe g, A. Salomaa, eds.: The Ox o d Handbook o Memb ane
Compu ing, Ox o d Uni . P ess, 2010.
9. Gh. P˘aun, M.J. P´e ez-Jim´enez: Sol ing p oblems in a dis ibu ed way in memb ane
compu ing: dP sys ems, In e na ional Jou nal o Compu e s, Communica ion &
Con ol, V(2), 2010, 238–250.
10. Gh. P˘aun, M.J. P´e ez-Jim´enez: P and dP au oma a: A su ey. Rainbow o Compu e
Science (C.S. Calude e al., eds.), LNCS 6570, Sp inge , 2011, 102–115.
F on ie s o Memb ane Compu ing 191
11. Gh. P˘aun, M.J. P´e ez-Jim´enez: An infini e hie a chy o languages defined by dP
sys ems. Theo e ical Compu e Sci., 431 (2012), 4–12.
6 Spiking Neu al P Sys ems
Linqiang Pan, Tao Song
Key Labo a o y o Image P ocessing and In elligen Con ol
Depa men o Con ol Science and Enginee ing
Huazhong Uni e si y o Science and Technology, Wuhan, Hubei, China
[email p o ec ed], [email p o ec ed]
Applica ions o spiking neu al P sys ems a e p oposed and some p oblems
ela ed o such applica ions a e o mula ed.
Requi ed No ions: spiking neu on, SN P sys em, spiking neu al ne wo k
Spiking neu al P sys ems (SN P sys ems, o sho ) we e in oduced in [4] as
a class o dis ibu ed and pa allel compu ing models inspi ed by spiking neu ons.
In an SN P sys em, he neu ons a e placed in he nodes o a di ec ed g aph.
The con en o each neu on consis s o a numbe o copies o a single objec ype,
called he spike. Each neu on con ains a numbe o fi ing and o ge ing ules.
Fi ing ules allow a neu on o send in o ma ion o o he neu ons in he o m o
elec ical impulses (also called spikes) which a e accumula ed a he a ge cells.
The applicabili y o each ule is de e mined by checking he con en o he neu on
agains a egula se associa ed wi h he ule. A o ge ing ule emo es a specified
numbe o spikes om he neu on. In each ime uni , i a neu on can use some o
i s ules, fi ing o o ge ing, hen one o he ules mus be used. The ule o be
applied is nonde e minis ically chosen.
One o he neu ons is designa ed as he ou pu neu on o he sys em, and
i s spikes a e also sen o he en i onmen ; hei sequence is called he spike ain
gene a ed by he sys em. Se e al esul s o a compu a ion can be defined associa ed
wi h he spike ain (s ings o numbe s).
SN P sys ems use indi idual spikes allowing o inco po a e spa ial and empo al
in o ma ion in compu a ion, which co esponds o he ac ha neu ons use spa ial
and empo al in o ma ion o incoming spikes o encode hei message o o he
neu ons, whe e he numbe and iming o spikes ma e s. In he abo e sense, SN
P sys ems all in o he hi d gene a ion o neu al ne wo k models [6].
Many compu a ional p ope ies o SN P sys ems ha e been s udied (bu many
o hem aise u he esea ch opics, bu we do no e e o hem he e). SN P sys-
ems we e p o ed o be compu a ionally comple e as numbe compu ing de ices
[4], language gene a o s [1, 2], and unc ion compu ing de ices [8]. SN P sys ems
we e also used o ( heo e ically) sol e compu a ionally ha d p oblems in a easible

192 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
ime [5, 7]. In con as wi h he ela i ely ich heo e ical esul s, he p ac ical
applica ions o SN P sys ems a e ew (al hough some a emp s a e al eady made,
e.g., Hebbian lea ning in he amewo k o SN P sys ems [3]). Howe e , as a ep e-
sen a i e o he hi d gene a ion o neu al ne wo k models, spiking neu al ne wo ks
(SNNs) could ha e e y hands-on applica ions such as speech ecogni ion, lea n-
ing, associa i e memo y, unc ion app oxima ion (see, e.g., In o ma ion P ocessing
Le e s, 95, 2005), and ha e p o ed o be use ul in neu oscience. I is in e es ing
o mo e he SN P sys ems in es iga ions owa ds applica ions. In he ollowing,
we lis some p oblems which we find o in e es .
•In SN P sys ems, he use o spike iming in o ma ion is based on egula ex-
p essions, which can be conside ed as an in eg a e-and-fi e scheme. The scheme
o egula exp essions is qui e diffe en om he adi ional ones, such as he
sigmoidal scheme. Wha is he ad an age o he scheme o egula exp essions
om he applica ion poin o iew? Can he wo schemes ( he egula exp es-
sion and he sigmoidal one) be ela ed?
•Wha ing edien s can be added o SN P sys ems o p ac ical applica ions
(maybe, noise, andomness)?
•Wha a e he specific eal wo ld p oblems whe e SN P sys ems ha e a p ac ical
ad an age o e o he SNNs?
•How can some a ian s o SN P sys ems be designed such ha hey would deal
wi h ea u es o mo e biological plausibleness?
Re e ences
1. H. Chen, M. Ionescu, T.-O. Ishdo j, A. P˘aun, Gh. P˘aun, M.J. P´e ez-Jim´enez: Spiking
neu al P sys ems wi h ex ended ules: uni e sali y and languages. Na u al Compu ing,
7 (2008), 147–166.
2. H. Chen, R. F eund, M. Ionescu, Gh. P˘aun, M.J. P´e ez-Jim´enez: On s ing languages
gene a ed by spiking neu al P sys ems. Fundamen a In o ma icae, 75 (2007), 141–162.
3. M.A. Gu i´e ez-Na anjo, Ma io J. P´e ez-Jim´enez: Hebbian lea ning om spiking neu-
al P sys ems iew. P oc. WMC9 2008 (D. Co ne e al., eds.), LNCS 5391, Sp inge ,
Be lin, 2009, 217–230.
4. M. Ionescu, G. P˘aun, T. Yokomo i: Spiking neu al P sys ems. Fundamen a In o ma -
icae, 71 (2006), 279–308.
5. T.-O. Ishdo j, A. Lepo a i, L. Pan, X. Zeng, X. Zhang: De e minis ic solu ions o
QSAT and Q3SAT by spiking neu al P sys ems wi h p e-compu ed esou ces. Theo-
e ical Compu e Science, 411 (2010), 2345–2358.
6. W. Maass: The Thi d Gene a ion o Neu al Ne wo k Models. Technische Uni e si a
G ¨az, 1997
7. L. Pan, Gh. P˘aun, M.J. P´e ez-Jim´enez: Spiking neu al P sys ems wi h neu on di ision
and budding. Science China In o ma ion Sciences, 54 (2011), 1596–1607.
8. A. P˘aun, Gh. P˘aun: Small uni e sal spiking neu al P sys ems. BioSys ems, 90 (2007),
48–60.
F on ie s o Memb ane Compu ing 193
7 Con ol Wo ds Associa ed wi h P Sys ems
Kamala K i hi asan1, Gheo ghe P˘aun2, Ajeesh Ramanujan1
1Depa men o Compu e Science and Enginee ing
Indian Ins i u e o Technology Mad as, Chennai, India
[email p o ec ed]
2Ins i u e o Ma hema ics o he Romanian Academy
Bucha es , Romania, and
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
Ways o associa e a con ol wo d wi h a compu a ion in a P sys em a e p o-
posed and some o he p oblems which a e na u al o be in es iga ed in his espec
a e men ioned.
Requi ed No ions: Szila d language, Chomsky hie a chy, cell P sys em, SN P
sys em, pa allelism
Con ol wo ds a e almos ne e conside ed in memb ane compu ing – ac ually,
we know no pape dealing wi h his issue, al hough gene a ing o ecognizing
languages a e cen al esea ch opics (wi h he languages iden ified by he sequence
o symbols en e ing o lea ing a P sys em, o by aces o ce ain symbols in hei
passage ac oss memb anes). The eason is he ac ha in he same s ep o a
compu a ion se e al ules a e used, possibly wi h se e al labels, hence he con ol
wo d is no clea ly defined. On he o he hand, a so o bidimensional con ol
wo d was in oduced al eady du ing he fi s BWMC, in [1], unde he name o
Se illa ca pe , as a way o desc ibe he ules used in a compu a ion and hei
mul iplici y in each s ep, bu no as a way o define a con ol language associa ed
wi h he compu a ions in a P sys em.
A possible solu ion o he abo e difficul y is o conside a sequence o mul i-
se s o labels, hose labels associa ed wi h all ules applied in a gi en s ep. Then,
a s ing o symbols can be ob ained ollowing he ideas also used o accep ing
P sys ems: ake a unc ion om mul ise s o s ings and build he s ing(s) ob-
ained by conca ena ing he s ings associa ed wi h he mul ise s. Fo ins ance, all
pe mu a ions o he labels in a mul ise can be conside ed, as in [3], o only one
specific s ing (maybe a symbol) associa ed wi h he mul ise , like in [2].
Ano he idea was ecen ly in oduced in [4], s a ing om he ollowing es ic-
ion: all ules used in a compu a ion s ep should ha e he same label, o hey can
also be labeled wi h λ.
The defini ion in [4] is gi en o SN P sys ems, bu i wo ks o any ype o P
sys ems, no only o SN P sys ems.
194 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
Indeed, le us conside a P sys em Π, o any ype, wi h he o al se o ules ( he
union o all se s o ules associa ed wi h compa men s, memb anes, neu ons – as
i is he case) deno ed wi h R. Conside a labeling mapping l:R→B∪{λ}, whe e
Bis an alphabe . We conside only ansi ions s=⇒bs′, be ween configu a ions
s, s′o Π, which use only ules wi h he same label band ules labeled wi h λ. We
say ha such a ansi ion is label es ic ed. Wi h a label es ic ed ansi ion we
associa e he symbol bi a leas one ule wi h label bis used; i all used ules ha e
he label λ, hen we associa e λ o his ansi ion. Thus, wi h any compu a ion in
Πs a ing om he ini ial configu a ion and p oceeding h ough label es ic ed
ansi ions we associa e a (con ol) wo d. Conside also a c i e ion Co he co ec
e mina ion o a compu a ion (e.g., hal ing o eaching a configu a ion om a
gi en se Fo final configu a ions, o bo h o hese, e c.) The language o con ol
wo ds associa ed wi h all label es ic ed compu a ions in Πwhich a e co ec ly
e mina ed (wi h espec o C) is deno ed by SzC(Π) (wi h Sz coming om Szila d,
as usual in language heo y).
Now, a se ies o na u al p oblems can be o mula ed: in es iga e he languages
o con ol wo ds o (i) a ious classes o P sys ems, wi h (ii) a ious c i e ia C, in
pa icula , (iii) allow only ansi ions which use a leas a ule labeled by b∈B.
When λ ansi ions a e accep ed, cha ac e iza ions o RE languages a e expec ed,
bu when each s ep p oduces a symbol, he e is no possibili y o “hidden wo k”,
he compu a ion has he same leng h as he con ol s ing, so ha he gene a ed
language is ecu si e. In his la e case he compa ison wi h language amilies in
Chomsky hie a chy is o in e es (wi h he conjec u e ha languages o he o ms
{xx |x∈V∗},{xxR|x∈V∗}, whe e ca d(V)≥2 and x is he mi o image o
x, canno be ob ained as he language o con ol wo ds o a P sys em.
In pa icula , he languages SzC(Π) can be associa ed wi h SN P sys ems,
wi h o wi hou an i-spikes. We expec in e es ing (language heo y) esul s in
his esea ch a ea.
Re e ences
1. G. Ciobanu, Gh. P˘aun, Gh. S¸ e ˘anescu: Se illa ca pe s associa ed wi h P sys ems.
P oc. B ains o ming Week on Memb ane Compu ing (M. Ca alie e e al., eds.), Ta -
agona Uni ., TR 26/03, 2003, 135–140.
2. E. Csuhaj-Va j´u, Gy. Vaszil: P au oma a o pu ely communica ing accep ing P sys-
ems. Memb ane Compu ing, In e na ional Wo kshop, WMC-CdeA, Cu ea de A ge¸s,
Romania, Augus 19-23, 2002, Re ised Pape s (Gh. P˘aun e al., eds.), LNCS 2597,
Sp inge , 2003, 219–233.
3. M. Oswald: P Au oma a, PhD Thesis, TU Viena, 2003.
4. A. Ramanujan, K. K i hi asan: Con ol wo ds o spiking neu al P sys ems. Pape in
p epa a ion.
F on ie s o Memb ane Compu ing 195
8 Speeding Up P Au oma a
Gy¨o gy Vaszil
Depa men o Compu e Science, Facul y o In o ma ics
Uni e si y o Deb ecen, Hunga y
[email p o ec ed]
The issue o efficien pa alleliza ion o languages wi h espec o dP au oma a
is discussed (especially, he dependence on he mul ise - o-s ings unc ions which
a e used o define he inpu language).
Requi ed No ions: Regula language, con ex -sensi i e language, P au oma a
and dP au oma a (accep ed mul ise sequence, inpu mapping, accep ed language)
This sec ion deals wi h he possibili y o speeding up P au oma a compu a ions
(in a simila sense as a linea speedup o Tu ing machines is possible), a p oblem
which is impo an om he poin o iew o he efficiency o he pa alleliza ion o
P au oma a compu a ions wi h dis ibu ed P au oma a.
AP au oma on, in oduced in [2], is an an ipo P sys em placed in an en i on-
men , om whe e a sequence o inpu mul ise s is ead du ing he compu a ion. A
mul ise sequence is accep ed, i he compu a ion ends in an accep ing configu a-
ion, and he accep ed mul ise sequence is in e p e ed as a s ing (a sequence o
symbols) using a so called inpu mapping :V∗→2T∗whe e Tis a fini e alphabe
and Vis he objec alphabe o he P au oma on. (We assume ha is none as-
ing, ha is, (u) is he emp y wo d o some mul ise u∈V∗, i and only i uis
emp y.) The language accep ed by a P au oma on Πwi h espec o is defined
as L(Π, ) = { ( 1). . . ( s)| 1,. . . , sis an accep ed mul ise sequence o Π}.
I is ob ious ha he choice o he mapping has a g ea influence on he
accep ing powe o he P au oma on, so le us ake a close look a he mappings
we can use.
Le :V∗→2T∗, and (1) le us deno e wi h pe m, i and only i V=T,
and o all ∈V∗, we ha e ( ) = {u|uis a pe mu a ion o }. Mo eo e , (2)
we say ha ∈TRANS, i and only i o any ∈V∗, we ha e ( ) = {w}
o some w∈T∗which is ob ained by applying a fini e ansduce o he s ing
ep esen a ion o he mul ise (as wis unique, he ansduce mus be cons uc ed
in such a way ha all s ing ep esen a ions o he mul ise as inpu esul in he
same w∈T∗as ou pu , and mo eo e , as should be none asing, he ansduce
p oduces a esul wi h w=λ o any nonemp y inpu ).
Le us ecall om [6] ha he e a e simple linea languages which canno be
accep ed by P au oma a wi h pe m, o example L={(ab)n(ac)n|n≥1}is
such a language. On he o he hand, he class o languages accep ed wi h pe m
also con ains non-con ex - ee con ex -sensi i e languages ({anbncn|n≥1} o
example), which means ha i is incompa able wi h he class o linea and o
con ex - ee languages. (Al hough i con ains all egula languages, see [3].) In
202 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
11 Seeking Sha pe F on ie s o Efficiency
in Tissue P Sys ems
Ma io J. P´e ez-Jim´enez1, Agus ´ın Riscos-N´u˜nez1,
Miquel Rius-Fon 2,´
Al a o Rome o-Jim´enez1
1Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
2Depa men o Applied Ma hema ics IV
Uni e si a Poli ´ecnica de Ca alunya, Cas elde els, Spain
[email p o ec ed]
In a P sys em, he e a e se e al ing edien s which concu o hei efficiency;
a ying hem, one can ge efficien sys ems (able o sol e compu a ionally ha d
p oblems in polynomial ime) o non-efficien sys ems (e.g., sol ing NP-ha d p ob-
lems in an exponen ial ime). The bo de line be ween efficiency and non-efficiency
is hus a p oblem o a cen al in e es . This issue is explo ed he e o issue P
sys ems, whe e he espec i e esea ch s a ed la e han o cell P sys ems.
Requi ed No ions: issue P sys ems, complexi y classes, cell di ision, cell sepa-
a ion, sympo /an ipo ule
A issue P sys em wi h sympo /an ipo ules Π= (Γ, E,M1, . . . , Mq,R, iou ),
o deg ee q≥1 can be iewed as a se o qcells, labeled by 1, . . . , q, wi h an
en i onmen labeled by 0 which ini ially ha e an a bi a y numbe o copies o some
kind o objec s, and a se o ules which can be o se e al ypes: communica ion,
di ision o sepa a ion (see [3, 4] o de ails).
Fo each na u al numbe k≥1, TDC(k) ( espec i ely, TDS(k) o TDA(k))
is he class o ecognize issue P sys ems wi h cell di ision and communica ion
ules (allowing only sympo o an ipo ules, espec i ely) o leng h a mos
k. Simila ly, by conside ing sepa a ion ules ins ead o di ision ules, we deno e
TSC(k), TSS(k) and TSA(k) espec i ely. We deno e by PMCR he se o all
decision p oblems which can be sol ed in a uni o m way and polynomial ime by
means o amilies o sys ems om a class Ro ecognize issue P sys ems.
(A) Tissue P sys ems wi h cell di ision and wi h cell sepa a ion
By using he dependency g aph echnique, i has been p o ed ha P=
PMCT DC(1) =PMCT SC(1) [2, 3]. Fu he mo e, efficien and uni o m solu ions
o he SAT p oblem by using sys ems om TDC(3) [1] and om TSC(8) [3] ha e
been gi en. Recen ly, he las esul has been imp o ed o SAT ∈PMCT SC(3) [6].
P oblem 1. Assuming P=NP, in he amewo k o issue P sys ems wi h cell
di ision/cell sepa a ion, a on ie o he ac abili y is ob ained when passing om
communica ion ules wi h leng h 1 o communica ion ules wi h leng h a mos 3.
Does passing om 1 o 2, amoun s o passing om non–efficiency o efficiency?

F on ie s o Memb ane Compu ing 203
Conjec u e: NP ∪co-b NP ⊆PMCT DC(2).
(B) The ole o di ec ion in communica ion ules
Nex , we deal wi h complexi y aspec s o issue P sys ems wi h cell di ison/celll
sepa a ion whe e only sympo o an ipo ules a e allowed. We ha e: P=
PMCT DA(1) =PMCT SA(1), and NP ∪co −NP ⊆PMCT DA(3) ∩PMCT SA(3).
Thus, assuming P=NP, a fi s on ie be ween efficiency and non-efficiency is
ob ained in he abo e amewo k when passing om communica ion ules wi h
leng h 1 o communica ion ules wi h leng h a mos 3.
P oblem 2. Wha abou he complexi y classes PMCT DA(2),PMCT SA(2),
PMCT DS(k)and PMCT SS(k), o all k≥1?
Conjec u e: P =PMCT SA(2), and o all k≥1, P=PMCT SS(k).
I his conjec u e is ue, hen passing om sympo ules o an ipo ules
wi h leng h a leas h ee, amoun s o passing om non–efficiency o efficiency, in
he amewo k o issue P sys ems wi h cell sepa a ion.
(C) The ole o he en i onmen
Classical issue P sys ems ha e a special alphabe associa ed wi h he en i-
onmen , whose elemen s appea a he ini ial configu a ion o he sys em, in an
a bi a y la ge amoun o copies. Wha may happen i his p ope y is emo ed,
ha is, i he alphabe associa ed o he en i onmen we e emp y? We use a “ha ”
o indica e he case when he en i onmen is ini ially emp y.
Recen ly, ha e been p o ed ha , o each k≥1, PMCT DC(k)=
PMC[
T DC(k)[5], ha is, in he amewo k o issue P sys ems wi h cell di ision
he ole o he en i onmen is no ele an om he complexi y poin o iew.
Conjec u e: Fo each k≥1, P=PMC[
T SC(k).
I his conjec u e is ue, hen in he amewo k o issue P sys ems wi h cell
communica ion he ollowing holds: (a) passing om sepa a ion ules o di ision
ules (leng h a leas h ee) amoun s o passing om non–efficiency o efficiency;
and (b) he en i onmen p o ides a new bo de line o efficiency.
Re e ences
1. D. D´ıaz, M.A. Gu i´e ez, M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez: A uni o m amily
o issue P sys ems wi h cell di ision sol ing 3-COL in a linea ime. Theo e ical
Compu e Science, 404 (2008), 76–87.
2. R. Gu i´e ez-Escude o, M.J. P´e ez-Jim´enez, M. Rius-Fon : Cha ac e izing ac abil-
i y by issue-like P sys ems. Memb ane Compu ing. 10 h In e na ional Wo kshop,
WMC 2009, Cu ea de A ge¸s, Augus 2009. Re ised Selec ed and In i ed Pape s,
LNCS 5957, Sp inge , Be lin, 2010, 289–300.
3. L. Pan, M.J. P´e ez-Jim´enez: Compu a ional complexi y o issue–like P sys ems.
Jou nal o Complexi y, 26 (2010), 296–315.
204 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
4. Gh. P˘aun, M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez: Tissue P sys ems wi h cell di ision.
In e na ional Jou nal o Compu e s, Communica ions & Con ol, 3 (2008), 295–303.
5. M.J. P´e ez-Jim´enez: The ole o he en i onmen in issue P sys ems wi h cell di i-
sion. Submi ed, 2012.
6. M.J.P´e ez-Jim´enez, P. Sos´ık: Imp o ing he efficiency o issue P sys ems wi h cell
sepa a ion. Submi ed, 2012.
12 Time-F ee Solu ions o Ha d Compu a ional P oblems
Ma eo Ca alie e
Na ional Cen e o Bio echnology, CNB - CSIC, Mad id, Spain
[email p o ec ed]
P sys ems a e usually synch onized, a unique clock ma ks he ime o all com-
ponen s, and in each ime uni each componen e ol es (usually, in he maximal
pa allel manne ). In ime- ee (and clock- ee) sys ems, his s ong assump ion is
emo ed. Up o now, he efficiency o P sys ems was no in es iga ed also o his
case.
Requi ed No ions: Time- ee P sys em, synch oniza ion, ecognizing P sys em,
uni o m/semi-uni o m solu ion.
12.1 Mo i a ions
Li ing cells ha e di ision a es ha a e highly he e ogeneous (e en in iden ical
en i onmen al condi ions), consequence o hei s ochas ic gene exp ession, [1].
The e o e, he possibili y o p og amming li ing cells should no assume he p es-
ence o uni o m eplica ion a es. Ideally, one should cons uc “cellula compu -
e s” whose unc ioning is independen o cellula di ision a es. We sugges ha
such p oblem can be add essed in he amewo k o memb ane compu ing by ex-
ending he no ion o ime- eeness ([4]) o he idea o semi-uni o m solu ions o
compu a ional p oblems based on memb ane di isions ([3]).
12.2 Timed Recognize P Sys ems
F om [4] we ecall he no ion o imed P sys em.
A imed P sys em Π(e) can be cons uc ed by adding o a (s anda d) P sys em
Πa ime-mapping e:R−→ N, whe e Ris he se o ules o Π. The ime-mapping
specifies he execu ion imes o he ules.
A imed P sys em Π(e) wo ks in he ollowing way. We suppose o ha e an
ex e nal clock ha ma ks ime-uni s o equal leng h (called s eps), s a ing om
s ep 0, when he sys em is p esen in i s ini ial configu a ion.
F on ie s o Memb ane Compu ing 205
A each s ep, all he ules ha can be s a ed, in each egion, and o each
memb ane ha e o be s a ed (maximal pa allel and nonde e minis ic use o ules).
When a ule is s a ed a s ep j, hen i s execu ion e mina es ( he ule is com-
ple ed) a s ep j+e( ), ha means he ule las s e( )s eps. The objec s and he
memb anes p oduced by he ule a e a ailable – can be subjec o o he ules – only
s a ing om he s ep j+e( )+1.When a ule is s a ed, hen he occu ences o
symbol-objec s and he memb ane subjec by his ule canno be anymo e subjec
o o he ules.
A compu a ion hal s when no ule can be s a ed in any egion and he e
a e no ules in execu ion (such configu a ion is called hal ing). We say ha he
compu a ion hal s in ks eps, i he ex e nal clock ma ks s ep kwhen he las ules
o he compu a ions a e comple ed.
F om [3] we ecall he no ion o ecognize P sys ems. A decision p oblem X
is a pai (IX, ΘX) whe e IXis a coun able language o e a fini e alphabe ( he
elemen s a e called ins ances), and ΘXis a p edica e (a o al boolean unc ion)
o e IX.
A ecognize P sys em is a P sys em such ha : (i) he wo king alphabe con ains
wo dis inguished elemen s yes and no; (ii) all compu a ions hal ; and (iii) i Cis
a compu a ion o he sys em, hen ei he objec yes o objec no (bu no bo h)
mus ha e been eleased in o he en i onmen , and only when he las ules o he
compu a ion ha e been comple ed.
We ex end ecognize P sys ems by p oposing he ollowing imed a ian : a
ecognize imed P sys em is a imed P sys em wi h p ope ies (i), (ii), (iii) abo e.
In ecognize imed P sys ems, we say ha a compu a ion is an accep ing com-
pu a ion ( espec i ely, ejec ing compu a ion) i he objec yes ( espec i ely, no)
appea s in he en i onmen associa ed wi h he co esponding hal ing configu a-
ion.
12.3 Time-F ee Solu ions o Decision P oblems
Le X= (IX, ΘX) be a decision p oblem. Le Π=Πu, u ∈IX, a (coun able)
amily o ecognize P sys ems.
We say ha he amily Πis sound (wi h espec o X) i o each ins ance o
he p oblem u∈IXsuch ha he e exis s an accep ing compu a ion o Πu, we
ha e ΘX(u) = 1.
We say ha he amily Πis comple e (wi h espec o X) i o each ins ance o
he p oblem u∈IXsuch ha ΘX(u) = 1, e e y compu a ion o Πuis an accep ing
compu a ion.
We say ha he amily Πis polynomially bounded i he e exis s a polynomial
unc ion p(n) such ha , o each u∈IX, all compu a ions in Πuhal s in, a mos ,
p(|u|) s eps.
We can now o malize he o iginal mo i a ions: A solu ion o a p oblem is ime-
ee i i s soundness, i s comple eness and i s polynomial bound do no depend on
he ime o execu ion associa ed o he ules o he cons uc ed sys ems.
206 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
We say ha he amily Πis ime- ee sound (wi h espec o X) i , o any
ime-mapping e, he amily Πe=Πu(e), u ∈IX, is sound wi h espec o X.
We say ha he amily Πis ime- ee comple e (wi h espec o X) i , o any
ime-mapping e, he amily Πe=Πu(e), u ∈IX, is comple e wi h espec o X.
We say ha he amily Πis ime- ee polynomially bounded i , o any ime-
mapping e, he amily Πe=Πu(e), u ∈IX, is polynomially bounded.
We can now adap he defini ion o semi-uni o m solu ions, as gi en in [3], and
conside ime- ee semi-uni o m solu ions.
Le X= (IX, ΘX) a decision p oblem. We say ha Xis sol able in a ime-
ee polynomial ime by a amily o ecognize P sys ems Π=Πu, u ∈IX, i he
ollowing a e ue:
• he amily Πis polynomially uni o m by a Tu ing machine; ha is, he e exis s
a de e minis ic Tu ing machine wo king in polynomial ime which cons uc s
he sys em Πu om he ins ance u∈IX.
• he amily Πis ime- ee polynomially bounded.
• he amily Πis ime- ee sound and ime- ee comple e (wi h espec o X).
We say ha he amily Πis a ime- ee semi-uni o m solu ion o he decision
p oblem X.
In o he wo ds, o p o ide a ime- ee solu ion one mus cons uc he amily o
sys ems Πin polynomial ime (sequen ial ime by de e minis ic Tu ing machines)
and he cons uc ed amily mus be “ as ” (polynomially bounded), sound and
comple e wi h espec o he conside ed p oblem X, and hese p ope ies mus
be independen o he execu ion ime o he ules (i.e., hey mus be ulfilled
independen ly o he ime-mapping conside ed).
The defini ion o ime- ee semi-uni o m solu ion cap u es he p oblem in o -
mally discussed in he Mo i a ions. The basic ques ion consis s in finding a class
o memb ane sys ems o which i is possible o cons uc ime- ee semi-uni o m
solu ions o ha d compu a ional p oblems. The simples possibili y is o ans o m
he solu ions al eady p esen in li e a u e in o ime- ee solu ions (e.g., could he
solu ion gi en in [2] be adap ed o become a ime- ee solu ion?).
Ano he in e es ing p oblem is o find classes o memb ane sys ems ha a e
powe ul enough o sol e complex p oblems, bu simple enough o allow an au o-
ma ic (i.e., algo i hmic) checking o hei ime- eeness.
Re e ences
1. M.B. Elowi z, J. Le ine, E.D. Siggia, P.S. Swain: S ochas ic gene exp ession in a
single cell. Science, 297 (2002), 5584.
2. Gh. P˘aun: P sys ems wi h ac i e memb anes: A acking NP comple e p oblems.
Jou nal o Au oma a, Language and Combina o ics, 6 (2001), 75–90.
3. M.J. P´e ez-Jim´enez, A. Riscos-N´u˜nez, A. Rome o–Jim´enez, D. Woods: Complexi y
– memb ane di ision, memb ane c ea ion. Chap e 12 in [5], 302–336.
F on ie s o Memb ane Compu ing 207
4. M. Ca alie e, D. Sbu lan: Time-independen P sys ems. Memb ane Compu ing. In .
Wo kshop WMC 2004, Milan, I aly, 2004 (G. Mau i e al., eds.), LNCS 3365,
Sp inge , 2005, 239–258.
5. Gh. P˘aun, G. Rozenbe g, A. Salomaa, eds.: The Ox o d Handbook o Memb ane
Compu ing. Ox o d Uni . P ess, 2010.
13 Fype compu a ions
Gheo ghe P˘aun
Ins i u e o Ma hema ics o he Romanian Academy
Bucha es , Romania, and
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
Following he model o hype compu a ion (compu ing beyond he “Tu ing ba -
ie ”), we p opose he e he e m ype compu a ion o name he esea ch a ea o
“sol ing polynomially p oblems which a e (a leas ) NP-comple e”. Some ideas
om/ o MC a e men ioned.
Requi ed No ions: memb ane di ision, memb ane c ea ion, hype compu ing,
SN P sys em, eac ion sys em, accele a ed P sys em
Looking o ideas which would lead o compu ing de ices able o compu e “be-
yond he Tu ing ba ie ” is al eady a well es ablished esea ch a ea o compu ing
heo y; such de ices a e said o be able o doing hype compu a ions. I is also a
d eam and a conce n o compu abili y o speed-up compu ing de ices; a name
was p oposed in [7] ( he idea was u he elabo a ed in [8]) o he case when his
leads o polynomial solu ions o p oblems known o be (a leas ) NP-comple e:
ype compu ing – wi h he ini ial Fcoming om “ as ”.
In sho : ype compu ing means going polynomially beyond NP.
The model we ha e in mind is ha o hype compu a ions, al eady wi h a la ge
li e a u e (we only men ion he ecen su ey om [10]). Mo e han a dozen o
ideas we e p oposed and p o ed o each he goal o compu ing “beyond Tu ing”:
o acles (al eady conside ed by Tu ing), in oducing eal numbe s in he de ice,
accele a ing he unc ioning o machines, using ing edien s o an analogical na u e
and so on. Many o hese ideas can p obably lead no only o hype compu a ions,
bu also o ype compu a ions, bo h in MC and in o he amewo ks.
Al hough no clus e ed unde a good name, such as hype compu a ion ( he e
a e pe iodical mee ings dedica ed o his esea ch di ec ion), he e also a e many

208 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
pape s which can be placed unde he flag o ype compu ing. They exploi ideas
om physics, such as [9], p opose analogical compu a ions, such as [1]. Also he
a ea o DNA compu ing is ull o such ideas.
The li e a u e o memb ane compu ing abounds in pape s dealing wi h ype -
compu a ions. In mos cases, polynomial solu ions o NP-comple e p oblems –
o en, also o PSPACE-comple e p oblems – a e ob ained, by making use o a
space- ime ade-off, wi h he space ob ained du ing he compu a ion, by means
o ope a ions inspi ed om biology. The mos in es iga ed ope a ions o his kind
a e memb ane di ision (wi h a ian s: sepa a ion, budding, e c.) and memb ane
c ea ion.
Fu he wo simila ideas we e also explo ed. The fi s one is based on s ing
eplica ion (see [3] o de ails), he second one is ha o conside ing a bi a ily la ge
p e-compu ed esou ces (see, e.g., [6]), bu he las idea is only b iefly in es iga ed
so a . Issues ela ed o he condi ions o be imposed o he gi en p e-compu ed
esou ces should be u he conside ed.
Th ee mo e ideas, essen ially diffe en om he p e ious ones, we e p oposed
in [8] and need addi ional esea ch effo s.
(1) The fi s candida e is he accele a ion, an old one in compu e science: a
“cle e ” compu ing de ice lea ns om i s own unc ioning; a e pe o ming a s ep
in a ime uni , i pe o ms be e o he second s ep, which is comple ed in hal
o he ime necessa y o he fi s s ep – and so on, a each s ep hal ing he ime
wi h espec o he p e ious s ep. I he fi s s ep akes one ime uni , hen he
second one akes 1/2 ime uni s, he hi d one 1/4 and so on, hence in wo ime
uni s he compu a ion ends.
Impo an : we ha e he e wo clocks, an in e nal one, o he machine, and an
ex e nal one, o he obse e . The in e nal clock is as e and as e , so ha he
compu a ion ends in wo ime uni s measu ed by he ex e nal clock, ha o he
obse e /use .
Accele a ed Tu ing machines can sol e he hal ing p oblem, hence hey com-
pu e wha usual Tu ing machines canno . See e e ences in [2], whe e he idea is
ex ended o P sys ems: s a ing om he biological obse a ion ha “smalle is
as e ” and using memb ane c ea ion ules o c ea e “ as e eac o s” (inne mem-
b anes), in an unbounded hie a chy, one can ob ain P sys ems which “compu e
he uncompu able”.
This ick can be used also in complexi y, bu we ha e o be cau ious: we ac-
cele a e in o de o ge a speed-up... In wo (ex e nal) ime uni s we sol e any
p oblem, wha e e complex i is. A way o make he hings in e es ing is o ac-
cele a e only pa s o a P sys em, hus ha ing se e al le els o ime speed. Fo
ins ance, we can accele a e only (i) some elemen a y memb anes, o (ii) only some
ules (a gi en ule akes one ime uni o he fi s applica ion, hal o he second
applica ion, and so on), o (ii) o ha e “accele a ed objec s” ( he descendan s o
an objec eac as e han he a he objec , i espec i e which a e he ules which
ac on hem and i espec i e o he memb anes whe e hey a e). P ecise defini ions
should be ound and hei use ulness explo ed.
F on ie s o Memb ane Compu ing 209
(2) The p e ious ideas sugges he ollowing specula ion. We men ioned ha
we ha e (a leas ) wo clocks, an ex e nal one, o he obse e (o o he highe
memb anes in he s uc u e) and he local clock(s), o he accele a ed elemen ,
memb ane, ule, objec . Always, he inne clock is (much) as e han he ex e nal
one, i pe o ms some imes an exponen ial numbe o s eps while he ex e nal one
only icks once. We can hen imagine ha he inne ime is o hogonal o he
ex e nal ime, hence he ime has a 2D s uc u e: he obse e only senses one
dimension o ime, bu ce ain “p ocesso s” can un along he o he dimension,
doing compu a ions a -no- ime o he obse e . This looks e y much as using
o acles. Again, good defini ions ha e o be ound and explo ed.
(3) One u he idea, p o ed in [8] o lead o ype compu a ions comes om
he ecen ly in oduced eac ion sys ems (we call hem R sys ems) – see [4], [5].
One o he c ucial pos ula es o R sys ems conce ns he ac ha one wo ks wi h
ωmul ise s: an objec ei he is no p esen , o i is p esen in a bi a ily many
copies. This assump ion can be ex ended also o P sys ems. Mo e exac ly, we
conside P sys ems which con ain ce ain dis inguished elemen a y memb anes,
whose objec s a e p esen in a bi a ily many copies ( o ins ance, i an objec
ais in oduced om ou side in such a memb ane, hen inside he memb ane i
immedia ely becomes aω). In [8], such a sys em is called ωP sys em and i is
p o ed ha SAT can be sol ed (in a uni o m way) in a polynomial ime by an ωP
sys em.
The cons uc ion in [8] uses coope a i e ules; we do no know whe he he
esul can be imp o ed by imposing he es ic ion o use only non-coope a i e
ules.
Re e ences
1. J.J. A ulanandham, C.S. Calude, M.J. Dinneen: Balance machines: compu ing =
balancing. Aspec s o Molecula Compu ing, 2004, LNCS 2950, Sp inge , 2004, 148–
161.
2. C.S. Calude, Gh. P˘aun: Bio-s eps beyond Tu ing. BioSys ems, 77 (2004), 175–194.
3. J. Cas ellanos, Gh. P˘aun, A. Rod iguez-Pa ´on: Compu ing wi h memb anes: P sys-
ems wi h wo m-objec s. P oc. IEEE 7 h. In e n. Con . on S ing P ocessing and
In o ma ion Re ie al, SPIRE 2000, La Co una, Spain, 2000, 64–74.
4. A. Eh en euch , G. Rozenbe g: Basic no ions o eac ion sys ems, P oc. DLT 2004,
LNCS 3340, Sp inge , 2004, 27–29.
5. A. Eh en euch , G. Rozenbe g: Reac ion sys ems. Fundamen a In o ma icae, 75
(2007), 263–280.
6. T.-O. Ishdo j, A. Lepo a i: Uni o m solu ions o SAT and 3-SAT by spiking neu al
P sys ems wi h p e-compu ed esou ces. Na u al Compu ing, 7 (2008), 519–534.
7. Gh. P˘aun: Memb ane compu ing a wel e yea s. Back o Tu ku. P oc. UC 2011,
Tu ku, Finland, June 2011, LNCS 6714, Sp inge , 2011, 36–37.
8. Gh. P˘aun: Towa ds “ ype compu a ions” (in memb ane compu ing), LNCS 6714,
Sp inge , 2011, 36–37.
210 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
9. V. Pu z, K. S ozil: Can a compu e be “pushed” o pe o m as e - han-ligh ? P oc.
UC10 Hype compu a ion Wo kshop “Hype Ne 10”, Uni . o Tokyo, June 22, 2010.
10. A. Sy opoulos: Hype compu a ion: Compu ing Beyond he Chu ch-Tu ing Ba ie .
Sp inge , 2008.
14 Nume ical P Sys ems
C is ian Ioan Vasile1, Ana B ˆandu¸sa Pa el1,
Ioan Dumi ache1, Gheo ghe P˘aun2
1Depa men o Au oma ic Con ol and Sys ems Enginee ing
Poli ehnica Uni e si y o Bucha es , Romania
{c asile, apa el, idumi ache}@ics.pub. o
2Ins i u e o Ma hema ics o he Romanian Academy
Bucha es , Romania, and
Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
Ex ensions o nume ical P sys ems mo i a ed by using such sys ems in obo
con olling a e men ioned and p oblems occu ing in his amewo k a e o mu-
la ed.
Requi ed No ions: nume ical P sys em, complexi y, p omo e s-inhibi o s, ca a-
lys
Nume ical P sys ems a e a class o compu ing models (in oduced in [5]; see
also Chap e 23.6 o [6]) inspi ed bo h om he cell s uc u e and economics:
nume ical a iables e ol e in he compa men s o a cell-like s uc u e by means o
so-called p oduc ion– epa i ion p og ams. The a iables ha e a gi en ini ial alue
and he p oduc ion unc ion is usually a polynomial, whose alue o he cu en
alues o a iables is dis ibu ed among a iables in he neighbo ing compa men s
acco ding o he “ epa i ion p o ocol”. In his way, he alues o a iables e ol e;
all posi i e alues aken by a specified a iable a e said o be compu ed by he P
sys em.
These sys ems we e ecen ly used in a se ies o pape s (see e e ences in [1]) o
implemen ing con olle s o mobile obo s; in his amewo k he P sys ems wo k
in he compu ing mode: an inpu is in oduced in he o m o he alues o some
a iables and an ou pu is p oduced, as he alue o o he a iables. Fu he mo e,
in he obo con ol con ex , he so-called enzyma ic nume ical P sys ems we e
in oduced and used, [2], [3], [4]. Such sys ems co espond o ca aly ic P sys ems
F on ie s o Memb ane Compu ing 211
in he “gene al” memb ane compu ing: a p og am is applied only i he alue o
he associa ed enzyme is s ic ly g ea e han he smalles alue o any a iable
in ol ed in he p oduc ion polynomial. Enzyme a iables a e no consumed o
p oduced by he ules which hey ca alyze, bu can be changed by he ules o
which hey do no ac as ca alys s. The e o e, hei alues can e ol e du ing he
compu a ional p ocess.
Tissue nume ical P sys ems a e also conside ed in [8], wi h pa allel use o
p og ams. I in each memb ane, a each s ep, we use a maximal se o p og ams
(p og ams a e selec ed nonde e minis ically, and a se o p og ams is applied only
i i is maximal, no u he p og am can be added o i in such a way ha he new
se is s ill applicable). Two possibili ies appea : (i) a a iable can appea only in
one p oduc ion unc ion, and his is he only es ic ion in choosing (nonde e min-
is ically) he p og ams o apply in a s ep, and (ii) i wo o mo e p og ams which
a e enabled a a compu a ion s ep, i.e., hey sa is y he condi ion imposed by he
associa ed enzymes, sha e a iables in hei p oduc ion unc ions, hen hey will
all use he cu en alues o hose a iables (we deno e his wi h allP).
A la ge a ie y o classes o nume ical P sys ems appea s in his way: (1)
enzyma ic o non-enzyma ic, (2) de e minis ic o nonde e minis ic, (3) sequen ial,
all-pa allel, one-pa allel, (4) used in he gene a ing, compu ing, accep ing mode;
u he a ian s can be added. By combining all hese, a ple ho a o classes o
nume ical P sys ems appea .
We do no ecall he e he defini ion o nume ical P sys ems, wi h o wi hou
enzyme con ol, bu we e e he eade o he pape s men ioned abo e.
We only men ion ha he amily o se s o numbe s N+(Π) compu ed by
nume ical P sys ems Πwi h a mos mmemb anes, p oduc ion unc ions which a e
polynomials o deg ee a mos n, wi h in ege coefficien s, wi h a mos a iables
in each polynomial, is deno ed by N+Pm(polyn( ), seq), m ≥1, n ≥0, ≥0,
whe e he ac ha we wo k in he sequen ial mode (in each s ep, only one p og am
is applied) is indica ed by seq. I one o he pa ame e s m, n, is no bounded, hen
i is eplaced by ∗. (Bo h in N+(Π) and in N+Pm(polyn( ), seq), he supe sc ip
+ indica es he ac ha as he esul o a compu a ion we only conside posi i e
na u al numbe s, ze o excluded. I any alue is accep ed, hen we emo e he
supe sc ip +.) When issue sys ems a e used, we w i e N Pm(polyn( ), α, β).
He e a e a ew esul s om [5] and [8].
Theo em 1. NRE =N+P8(poly5(5), seq) = N+P7(poly5(6), seq) =
NP7(poly5(5), enz, seq) = N P∗(poly1(11), enz, oneP) =
NP254(poly2(253), enz, allP, de ).
Whe he o no he pa ame e s appea ing in hese esul s a e op imal o no
is an open p oblem.
Only a ew o he many cases men ioned abo e we e so a in es iga ed, he
o he ones wai o esea ch effo s.
In pa icula , we ha e seen ha enzymes imp o e he uni e sali y esul s in
e ms o he complexi y o used polynomials, bo h in he cell-like case and he
218 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
The ype sys ems can be used in defining mo e gene al and simple ules o P
sys ems. Fo example, i N1and N2a e some basic ypes, by conside ing a se o
yped objec s V={X1:N1,X2:N1,X3:N1,A:N2}, he e olu ion ules o
he o m Xi→Xj,Xj→A, 1 ≤i≤3, 1 ≤j≤3, can be eplaced by ules o a
mo e gene al o m:
1. N1→N1(any objec o ype N1can e ol e in any objec o ype N1);
2. N1→N2(any objec o ype N1can e ol e in any objec o ype N2).
16.4 Beha io Equi alence
Beha io equi alence is an impo an concep in biology needed o analyzing and
compa ing he o gans beha io . Fo example, an a ificial o gan is he unc ional
equi alen o he na u al o gan, meaning ha bo h beha e in a simila manne up
o a gi en ime; e.g. he a ificial kidney has he same unc ional cha ac e is ics as
an “in i o” kidney. Recen ly, i is shown in [7] ha he as de e ens’ o he human,
canine, and bull a e equi alen in many ways, including his ological simila i ies.
In [6] a e p esen ed diffe en me hods o compa ing p o ein s uc u es in o de o
disco e common pa e ns.
In memb ane compu ing, wo P sys ems a e conside ed o be equi alen when-
e e hey ha e he same inpu /ou pu beha io . Such an equi alence does no ake
ca e o he e olu ion o he wo sys ems. Wha does i mean ha wo P sys ems
ha e equi alen ( imed) beha io ? Defining se e al equi alences, we offe flexibili y
in selec ing he igh one when e i ying biological sys ems and compa ing hem.
When a P sys em can be eplaced in a con ex wi h ano he one such ha he
obse ed beha io is he same?
Re e ences
1. O. Ag igo oaiei, G. Ciobanu: Re e sing compu a ion in memb ane sys ems. Jou nal
o Logic and Algeb aic P og aming, 79 (2010), 278–288.
2. O. Ag igo oaiei, G. Ciobanu: Rule-based and objec -based e en s uc u es o mem-
b ane sys ems. Jou nal o Logic and Algeb aic P og aming, 79 (2010), 295–303.
3. O. Ag igo oaiei, G. Ciobanu: Quan i a i e causali y in memb ane sys ems. P oc.
Twel h In e na ional Con e ence on Memb ane Compu ing, Fon ainebleau, 2011, 53–
63.
4. B. Aman, G. Ciobanu: Typed memb ane sys ems. In . Wo kshop on Memb ane
Compu ing, WMC 2009, LNCS 5957, Sp inge , 2010, 169–181.
5. G. Be y, G. Boudol: The chemical abs ac machine. Theo e ical Compu e Science,
96 (1992), 217–248.
6. I. Eidhamme , I. Jonassen, W. Taylo : S uc u e compa ison and s uc u e pa e ns.
Jou nal o Compu a ional Biology, 7 (2000), 685–716.
7. D.E. Leocadio, A.R. Kunselman, T. Coope , J.H. Ba an es, J.C. T ussell: Ana om-
ical and his ological equi alence o he human, canine, and bull as de e ens. The
Canadian Jou nal o U ology, 18 (2011), 5699–5704.

F on ie s o Memb ane Compu ing 219
8. Gh. P˘aun: Some open p oblems collec ed du ing 7 h BWMC. P oc. Se en h B ain-
s o ming Week on Memb ane Compu ing, 2009, ol. 2, 197–206.
9. B. Russell: The P inciples o Ma hema ics, ol. I, Camb idge Uni e si y P ess, 1903.
10. J. Wells: The essence o p incipal ypings. LNCS 2380, Sp inge , 2002, 913–925.
17 Ke nel P Sys ems
Ma ian Gheo ghe
Depa men o Compu e Science, Uni e si y o Pi e¸s i, Romania
Depa men o Compu e Science, Uni e si y o Sheffield, UK
[email p o ec ed]
The issue o a common gene aliza ion o se e al classes o P sys ems is p oposed,
and some basic ideas owa ds such a goal a e p esen ed.
Requi ed No ions: issue P sys em, P sys em wi h dynamic s uc u e, egula
exp ession
Diffe en a ian s o P sys ems ha e been used o speci ying simple algo i hms
[5, 2], classes o NP-comple e p oblems [7] and a ious applica ions [6]. Mo e
specific classes o P sys ems ha e been ecen ly conside ed o modeling some
dis ibu ed algo i hms and p oblems [8]. In many cases he e olu ion o he sys em
in es iga ed equi es some specific beha io o he use o ce ain ules, maybe
wi h some cons ain s, which a e no always he same as he ones exhibi ed by
he model in i s ini ial defini ion. I helps in many cases o ha e some flexibili y
wi h he modeling app oach, especially in he specifica ion s age, as i sho ens he
model and makes i clea e . Al hough he e is a powe ul specifica ion language,
called P-lingua, wi h implemen a ions o a ious a ian s o P sys ems [9], he e
is no unified amewo k ha allows us o simula e, e i y and es he beha io o
he specified sys ems. In his espec , i is sugges ed he e a ke nel P sys em (kP
sys em, o sho ) ha , in he fi s s age, will be a low le el specifica ion language
including he mos used concep s om P sys ems.
The gene ic s uc u e o a kP sys em migh be a g aph-like s uc u e as in
issue P sys ems. Such a model uses a se o symbols, labels o memb anes, ules
o a ious ypes and a ce ain s a egy o un hem agains he mul ise o ob-
jec s a ailable in each egion. The ules in each compa men will be o wo ypes:
(i) objec p ocessing ules which ans o m and anspo objec s be ween com-
pa men s o exchange objec s be ween compa men s and en i onmen , and (ii)
sys em s uc u e ules esponsible o changing he sys em’s opology. Each ule
has a gua d, defined using ac i a o s and inhibi o s in a gene al way. The execu ion
s a egy is defined such ha maximally pa allel o sequen ial manne s a e cap u ed
220 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
and each compa men has i s own s a egy. Rew i ing and communica ion ules
based on p omo e s and inhibi o s a e conside ed oge he wi h a special se o
sympo /an ipo ules. Addi ional ea u es like memb ane di ision, c ea ion, dis-
solu ion, bond c ea ion and des uc ion a e used o deal wi h he sys em s uc u e.
The key concep o a compa men is fi s in oduced and hen he defini ion
o a kP sys em.
De ini ion 1. Gi en an alphabe A, o elemen s named objec s, and an alphabe
Lo labels, a compa men is a uple C= (l, w0, Rσ), whe e l∈Lis he label
o he compa men , w0is he ini ial mul ise o e A, and Rσdeno es “ he DNA
code”, i.e., he se o ules, deno ed R, applied in his compa men and a egula
exp ession, σ, o e Lab(R), he labels o he ules o R.
De ini ion 2. Ake nel P sys em is a uple kΠ = (A, L, IO, µ, C1, . . . , Cn), whe e
Aand La e, as in Defini ion 1, he alphabe o objec s and he se o labels,
espec i ely; IO is a mul ise o objec s om A, called en i onmen ;µdefines
he memb ane s uc u e, which is a g aph, (V, E), whe e Va e e ices, V⊆L
( he nodes a e labels o hese compa men s), and Eedges; C1, . . . , Cna e he n
compa men s o he sys em – he inne pa o each compa men is called he
egion which is delimi ed by a memb ane; he labels o he compa men s a e om
Land ini ial mul ise s a e o e A.
We fi s discuss a ious ypes o ules. I is assumed ha he ules below
belong o he same compa men , Ci, labeled li. Each ule migh ha e a egula
exp ession associa ed wi h. When a ule in ol es mo e han a compa men , hen
each compa men migh ha e i s own egula exp ession a ached o i . RE(A∪¯
A)
deno es he se o egula exp essions o e A∪¯
A; each such egula exp ession de-
fines condi ions in ol ing p omo e s, elemen s om A, and/o inhibi o s, elemen s
om ¯
A. The in e p e a ion o a egula exp ession g∈RE(A∪¯
A), associa ed
wi h a ule, is ha all he p omo e s appea ing in gmus be p esen in he cu en
mul ise and none o he inhibi o s mus appea he e. We call his egula exp es-
sion, g,gua d. A ule wi h such a gua d is applicable when his is e alua ed o ue.
A ule can ha e one o he ollowing ypes:
• ew i ing and communica ion ule: x→y{g}, whe e x∈A+,y∈A∗,
g∈RE(A∪¯
A); he igh hand side, y, has he o m y= (a1, 1). . . (ah, h),
whe e aj∈Aand j∈L, 1 ≤j≤h, is an objec and a a ge (i.e., he label
o a compa men ), espec i ely; he a ge jmus be ei he he label o he
cu en compa men , li(mo e o en igno ed) o o an exis ing neighbo o i
((li, j)∈E) o an unspecified one, ∗; o he wise, he ule is no applicable;
i a a ge j e e s o a label ha appea s mo e han once, hen one o he
in ol ed compa men s will be nonde e minis ically chosen; i jis ∗, hen he
objec ajis sen o a compa men a bi a ily chosen;
•inpu -ou pu ule, is a o m o sympo /an ipo ule: (x/y){g}, whe e x, y ∈
A∗,g∈RE(A∪¯
A); x om he cu en egion, li, is sen o he en i onmen
and y om he en i onmen is b ough in o he cu en egion;
F on ie s o Memb ane Compu ing 221
•sys em s uc u e ules; he ollowing ypes a e conside ed:
–memb ane di ision ule: []li→[]li1. . . []lih{g}, whe e g∈RE(A∪¯
A); he
compa men liwill be eplaced by hcompa men s ob ained om li, i.e.,
he con en o hem will coincide wi h ha o li; hei labels a e li1, . . . , lih,
espec i ely; all he links o lia e inhe i ed by each o he newly c ea ed
compa men s;
–memb ane dissolu ion ule: []li→λ{g}; he compa men liwill be
des oyed oge he wi h i s links;
–link c ea ion ule: []li; []lj→[]li−[]lj{cg}; he cu en compa men li
is linked o ljand, i mo e han one ljexis s, hen one o hem will be
nonde e minis ically picked up; cg, called compound gua d, desc ibes an
exp ession li.g1op lj.g2, whe e g1, g2a e egula exp essions e e ing o
compa men s liand lj, espec i ely; op is ei he and o o , s anding o
ei he bo h gua ds a e ue o a leas one is ue. I one o he gua ds
is emp y hen op is no longe used; a compound gua d defines a Boolean
condi ion ac oss he wo compa men s;
–link des uc ion ule: []li−[]lj→[]li; []lj{cg}; his is he opposi e o link
c ea ion and means ha compa men s li, lja e disconnec ed; as usual,
when mo e han a link, (li, lj)∈E, exis s, hen only one is conside ed by
his ule; cg is a compound gua d.
The usual beha io o P sys ems equi ing ha ew i ing and communica ion,
and sympo /an ipo (inpu -ou pu ) ules a e applied in a maximal pa al-
lel way (o sequen ially in some cases), whe eas memb ane di ision, c ea ion,
dissolu ion ules and c ea ion and des uc ion o links a e execu ed one pe
memb ane, will be conside ed in his con ex as well, bu in a a he mo e
gene al way.
The main challenges o his app oach a e
1. a igo ous defini ion o he syn ax and seman ics o kP sys ems;
2. compa isons be ween ( agmen s) o kP sys ems and well-known a ian s o P
sys ems;
3. es ablishing gene al algo i hms o ansla e diffe en classes o P sys ems in o
kP sys ems (simila o [1, 4]);
4. defining ope a ional seman ics o kP sys ems and p o iding implemen a ions
in model checke s, like Spin, Maude, simila o [3].
Fu he s eps in de eloping his unified amewo k migh consis o adding o he
use ul modeling ea u es like he possibili y o defining ules and compa men s
using indexes, a ce ain concep o a module, a ious o he seman ics. I is in ended
o keep he ke nel sys em as gene ic as possible such ha some o he abo e
men ioned ex ensions will be in oduced in a a he syn ac ical manne allowing
o map hem in o he basic a ian , wi hou addi ional seman ics.
Acknowledgemen . This wo k was pa ially suppo ed by p ojec MuVe , Roma-
nian Na ional Au ho i y o Scien ific Resea ch (CNCS, UEFISCDI) g an numbe
PN-II-ID-PCE-2011-3-0688.
222 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
Re e ences
1. A. Alhazo , L. Pan, Gh. P˘aun: T ading pola iza ions o labels in P sys ems wi h
ac i e memb anes. Ac a In o ma ica, 41 (2004), 111–144.
2. A. Alhazo , D. Sbu lan: S a ic so ing P sys ems. In [6], 2006, 215–252.
3. O. And ei, G. Ciobanu, D. Lucanu, A ew i ing logic amewo k o ope a ional
seman ics o memb ane sys ems. Theo e ical Compu e Sci., 373 (2007), 163–181.
4. R. Ba bu i, A. Maggiolo-Sche ini, P. Milazzo, S. Tini: Memb ane sys ems wo king
in gene a ing and accep ing modes: Exp essi eness and encodings. Memb ane Com-
pu ing, 11 h In e na ional Con e ence, CMC2010, Jena, Ge many, Augus 2010 (M.
Gheo ghe e al., eds), LNCS 6501, Sp inge , 2011, 103–118.
5. R. Ce e chi, C. Ma ´ın-Vide: P sys ems wi h communica ion o s a ic so ing. P e-
P oc. B ains o ming Week on Memb ane Compu ing, Ta agona, Feb ua y 2003 (M.
Ca alie e e al., eds.), Technical Repo no 26, Ro i a i Vi gili Uni ., Ta agona, TR
26/03, URV, 2003, 101–117.
6. G. Ciobanu, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.: Applica ions o Memb ane Com-
pu ing, Sp inge , 2006.
7. D. D´ıaz-Pe nil, M.A. Gu i´e ez-Na anjo, M.J. P´e ez-Jim´enez: A uni o m amily o
issue P sys ems wi h cell di ision sol ing 3-COL in a linea ime. Theo e ical Com-
pu e Science, 404 (2008), 76–87.
8. R. Nicolescu, M.J. Dinneen, Y.-B. Kim: S uc u ed modelling wi h hype dag P sys-
ems. Pa A. Memb ane Compu ing, Se en h B ains o ming Week, BWMC 2009,
Se illa, Spain, Feb ua y 2009 (A.R. Gu i´e ez-Escude o a al., eds.), Uni e sidad de
Se illa, 2009, 85–107.
9. The P-lingua Websi e: h p://www.p-lingua/wiki/index.php/Main Page.
18 B idging P and R
Gheo ghe P˘aun
Ins i u e o Ma hema ics o he Romanian Academy
Bucha es , Romania, and
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
Some possibili ies o b idging MC (P sys ems) and eac ion sys ems a e dis-
cussed, he basic idea being o impo ing ideas om a esea ch a ea o ano he
one.
Requi ed No ions: cell P sys em, mul ise , eac ion sys em, hal ing, ype com-
pu ing
Reac ion sys ems (we call hem R sys ems) o m a ecen ly in oduced esea ch
a ea aiming o model he e olu ion o (bio)chemicals by means o (bio) eac ions,
F on ie s o Memb ane Compu ing 223
in a amewo k based on he ollowing wo undamen al assump ions (we ecall
hem in he o mula ion om [1]):
The way ha we define he esul o a se o eac ions on a se o elemen s
o malizes he ollowing wo assump ions ha we made abou he chemis y o a
cell:
(i) We assume ha we ha e he “ h eshold” supply o elemen s (molecules) –
ei he an elemen is p esen and hen we ha e “enough” o i , o an elemen is
no p esen . The e o e we deal wi h a quali a i e a he han quan i a i e (e.g.,
mul ise s) calculus.
(ii) We do no ha e he “pe manence” ea u e in ou model: i no hing happens o
an elemen , hen i emains/su i es (s a us quo app oach). On he con a y,
in ou model, an elemen emains/su i es only i he e is a eac ion sus aining
i .
Wi h hese pos ula es in mind, le us conside fi s some possibili ies o passing
om R sys ems o P sys ems.
Mo ing om mul ise s, which a e basic in P sys ems, o se s (ac ually, o mul-
ise s wi h an infini e mul iplici y o hei elemen s, called ωmul ise s in Sec ion
13) is a undamen al assump ion, which changes comple ely he app oach; o in-
s ance, we can no longe define compu a ions wi h he esul exp essed in e ms
o coun ing molecules: he o al se o molecules is fini e, any molecule is ei he
absen o p esen in infini ely many copies.
Howe e , as we ha e men ioned in Sec ion 13, conside ing P sys ems wi h ω
mul ise s leads in an easy way o ype compu a ions.
The second assump ion o he eac ion sys ems heo y (no pe manence o ob-
jec s) looks easie o handle in e ms o MC. The immedia e idea is o simply
emo e (by a “dele ion ule”) any elemen which does no e ol e by means o a
eac ion; somewha equi alen ly, i we wan o p ese e an objec awhich is no
e ol ing, we may p o ide a dummy ule o i , o he ype a→a, changing no hing.
S ill, many echnical p oblems appea in his amewo k. The p esence o such
dummy ules makes he compu a ion endless, while hal ing is he “s anda d” way
o define success ul compu a ions in MC. Mo eo e , he ules a e nonde e minis-
ically chosen, hence he dummy ules can in e e e wi h he “compu ing ules”.
While he second difficul y is a pu ely echnical one, he fi s one can be o e -
passed by conside ing o he ways o defining he esul o a compu a ion in a P
sys em, and he e a e many sugges ions in he li e a u e. We men ion he e h ee
possibili ies: (i) he local hal ing ( he compu a ion s ops when a leas one mem-
b ane in he sys em canno use any ule), (ii) signal-objec s ( he esul consis s
o he numbe o objec s in a specified memb ane a he momen when a dis in-
guished objec appea s in he sys em), (iii) signal-e en s ( he esul consis s o he
numbe o objec s in a specified memb ane a he momen when a dis inguished
ule is used in he sys em). Such possibili ies we e conside ed in a ious pape s in
MC.
Pa o hese possibili ies a e checked in [7] om whe e we ecall he ollowing
esul :

224 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
Theo em 2. T ansi ion P sys ems o deg ee 2, using coope a i e ules, wi hou
he pe manence o objec s, a e compu a ionally comple e when he success ul com-
pu a ions a e defined by local hal ing o signal-objec s. The same esul holds ue
o sympo /an ipo P sys ems (o deg ee 2 and o weigh 2) o he case o local
hal ing.
An in e es ing open p oblem in his amewo k is he case o ca aly ic P sys ems,
known o be uni e sal in he “pe manence” assump ion.
The case o defining he esul o a compu a ion o sympo /an ipo P sys ems
by means o signals – objec s o e en s – also emains as an open p oblem. (Con-
side ing a p io i y ela ion on each se o ules can easily sol e his p oblem.) The
sympo /an ipo P sys em used in he p oo o Theo em 2 [7] con ains an ipo
ules o sizes (2, 1) and (1, 2), which is “la ge” o uni e sali y esul s in he case
when objec s a e pe sis en . Can he size o ules be dec eased also in he case
discussed he e?
The R sys ems a ea has a se ies o no ions o he dynamical sys ems ype which
we e no oo much in es iga ed o P sys ems ( ime, e en s, modules, s uc u e,
causali y, and so on), and his is also a p omising di ec ion o esea ch.
Le us now b iefly explo e he o he di ec ion, om P o R.
The R sys ems a e no mean o define compu a ions, hei beha io is de-
e minis ic, om a se o symbols we p ecisely pass o a unique se o symbols.
Howe e , s a ing om an R sys em, a “gene a i e de ice” can be defined, based
on passing om a configu a ion o ano he one (wi hou inpu om he en i on-
men ), p o ided ha some nonde e minism is in oduced in he R sys em unc ion-
ing. Th ee possibili ies o his kind we e p oposed in [7]: (i) wo king wi h abled
R sys ems, as in Lindenmaye sys ems (in each s ep, a able is used, nonde e min-
is ically chosen), (ii) conside ing also a fini e mul iplici y o some o he objec s,
and (iii) by in oducing a gene al h eshold kon he numbe o ules which can use
he same molecule. All hese h ee possibili ies emain o be in es iga ed: p op-
e ies o he ob ained compu a ion g aphs, possible links wi h compu ing de ices
om o mal language and au oma a heo y, influence o he in oduced pa ame e s
(numbe o ables, h eshold k), possible hie a chies.
O cou se, a gene al esea ch opic is o find o he ways o building a (s ing
o g aph) compu ing de ice in e ms o R sys ems. A possible ques ion is also he
possibili y o in oduce memb anes in he R sys ems a ea o o he MC ing edien s
– hus ge ing a so o PR sys ems. (An a emp o his kind is epo ed in [5],
whe e so-called eac ion au oma a a e in oduced, bu hese de ices iola es bo h
pos ula es o R sys ems and use so many ing edien s o P sys ems – mul ise s,
pa allelism, nonde e minism, hal ing – ha hey a e jus P au oma a wi h a new
name.)
F on ie s o Memb ane Compu ing 225
Re e ences
1. A. Eh en euch , G. Rozenbe g: Basic no ions o eac ion sys ems, P oc. DLT 2004
(C.S. Calude e al., eds.), LNCS 3340, Sp inge , 2004, 27–29.
2. A. Eh en euch , G. Rozenbe g: Reac ion sys ems. Fundamen a In o ma icae, 75
(2007), 263–280.
3. A. Eh en euch , G. Rozenbe g: E en s and modules in eac ion sys ems. Theo e ical
Compu e Sci., 376 (2007), 3–16.
4. A. Eh en euch , G. Rozenbe g: In oducing ime in eac ion sys ems. Theo e ical
Compu e Sci., 410 (2009), 310–322.
5. F. Okubo, S. Kobayashi, T. Yokomo i: On he p ope ies o languages classes defined
by bounded eac ion au oma a. Theo e ical Compu e Sci., in p ess.
6. Gh. P˘aun: Towa ds ype compu a ions (in memb ane compu ing). LNCS, Sp inge ,
o appea .
7. Gh. P˘aun, M.J. P´e ez-Jim´enez: Towa ds b idging wo cell-inspi ed models: P sys ems
and R sys ems. Theo e ical Compu e Sci., o appea .
19 P Sys ems and E olu iona y Compu ing In e ac ions
Gexiang Zhang
School o Elec ical Enginee ing
Sou hwes Jiao ong Uni e si y, Chengdu, P.R. China
[email p o ec ed]
P oblems ela ed o he so-called memb ane algo i hms (ac ually, dis ibu ed
e olu iona y compu ing, wi h he dis ibu ion con olled by means o memb anes,
as well as wi h o he MC ing edien s used) a e men ioned, bo h in he di ec ion o
imp o ing he op imiza ion echniques and in looking o mo e complex/p ac ical
applica ions.
Requi ed No ions: e olu iona y compu ing, cell P sys em, ac i e memb anes,
memb ane algo i hm
As a ela i ely young b anch o na u al compu ing, MC has gone h ough hi -
een yea s o in ensi e esea ch in ol ing a eas o heo e ical compu e science as
well as applica ions in a ious fields, including sys ems biology, g aphics, linguis-
ics, pa allel and dis ibu ed compu ing. Howe e , hese applica ions, in e ms o
a ie ies and ypes, a e ela i ely small compa ed o a e y b oad ange o appli-
ca ions o e olu iona y compu ing. A na u al ques ion would be, whe he some
combina ions o hese wo models migh benefi om he la ge scope o applica-
ions e olu iona y compu ing has al eady shown so a , and he igo ous and sound
heo e ical de elopmen memb ane sys ems ha e p o ed o all i s a ian s.
226 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
The possible in e play be ween MC and e olu iona y compu a ion may p oduce
h ee kinds o esea ch opics:
Memb ane-inspi ed e olu iona y algo i hms (MIEAs): Since mem-
b ane compu ing was ini ia ed in 1998, a la ge numbe o heo e ical esul s, such
as a ious a ian s o memb ane sys ems and hei compu a ional powe and effi-
ciency came o h [1]. On he one hand, he way MC is ex ended in o eal-wo ld
applica ions is no easy o be add essed and ep esen s an ongoing issue. On he
o he hand, he hyb idiza ion o diffe en compu ing echniques is an a ac i e
esea ch opic in he a ea o e olu iona y compu ing, due o a be e pe o mance
han hei coun e pa app oaches. Wha can he young pa adigm o MC b ing
o e olu iona y compu a ion? Fo una ely, MIEAs, o me ly called memb ane al-
go i hms [2, 3], c ea e a b idge be ween MC and a ious eal-wo ld applica ions.
MIEA concen a es on gene a ing new e olu iona y algo i hms o sol ing op i-
miza ion p oblems by using he hie a chical o ne wo k s uc u es o memb anes
and ules o P sys ems, and he concep s and p inciples o me a-heu is ic sea ch
me hodologies [3, 4]. The compa a i e analysis o dynamic beha io s o an ins ance
o MIEAs shows he app op ia e combina ion o MC and e olu iona y compu a-
ion can p oduce a be e capabili y o balance explo a ion and exploi a ion [5],
which a e wo con adic o y ac o s di ec ly ela ed o he pe o mance o an op i-
miza ion algo i hm. Un il now, MIEAs ha e been s udied in conjunc ion wi h cell
P sys ems wi h a fixed memb ane s uc u e and by conside ing an e olu iona y
compu ing app oach as a subalgo i hm pu inside a memb ane [1, 6, 7]. Fu he
esea ch opics a e lis ed below.
1. Conside u he combina ions o ea u es ha make ull use o he cha ac e is-
ics o bo h MC models and e olu iona y compu ing, such as he conside a ion
o cell P sys ems wi h ac i e memb anes, issue P sys ems and popula ion P
sys ems.
2. Usually, in an MIEA an e olu iona y algo i hm is used as a subalgo i hm
placed inside a memb ane. This idea can be ex ended. A memb ane s uc u e
can be used as a amewo k o he o ganiza ion o se e al diffe en ypes o
e olu iona y ope a o s, as shown in [8], o se e al dis inc kinds o e olu iona y
mechanisms, such as a gene ic algo i hm, e olu iona y p og amming, e olu ion
s a egy, diffe en ial e olu ion and pa icle swa m op imiza ion. Fu he mo e,
he flexible communica ion ules can be used a he le el o genes, ins ead o
a he le el o indi iduals shown in [6, 4].
3. The single-objec i e p oblems a e usually in ol ed in he in es iga ions e-
po ed in he li e a u e. The amewo k o P sys ems can offe be e popula-
ion di e si y in MIEAs, hence u he wo k can u n o sol e p oblems in a
complex en i onmen , such as mul i-objec i e, dynamic, peaked op imiza ion
p oblems, and wi h/wi hou cons ain s, o check whe he P sys ems can b ing
a be e pe o mance o e olu iona y algo i hms.
4. Mo e eal-wo ld applica ion p oblems, such as powe sys em op imiza ion,
so wa e/ha dwa e co-design and ehicle ou e plan, can be sol ed by using
MIEAs.
F on ie s o Memb ane Compu ing 227
5. A deep pe o mance analysis and e alua ion o MIEAs is necessa y o e eal
he oles o P sys ems played in he hyb id op imiza ion algo i hms, on he
basis o he p e ious wo k [5].
Au oma ed design o memb ane compu ing models (ADMCMs): The
au oma ed syn hesis o some ypes o MC models o o a high le el specifica ion
o hem is en isaged o be ob ained by applying a ious e olu iona y algo i hms.
ADMCMs aim o ci cum en he p og ammabili y issue o memb ane based models
o complex sys ems [9]. This is qui e a complex p oblem as i in ol es a g ea
numbe o pa ame e s ( ules, objec s, combina ion o ules) and many seman ics
associa ed wi h P sys ems.
Memb ane e olu iona y algo i hms (MEAs): MEAs will ocus on im-
plemen ing e olu iona y algo i hms wi hin a P sys em en i onmen in o de o
ake ad an age o he pa allelism and dis ibu ion o MC, gi en ha ecen in es-
iga ions a e s udying he implemen a ion o P sys ems on pa allel o mul i-co e
ha dwa e pla o ms. An impo an challenge o any o he abo e esea ch de el-
opmen s will be o apply hem o complex eal li e sys ems.
Acknowledgemen . This wo k was suppo ed by he Na ional Na u al Science
Founda ion o China (61170016), he P og am o New Cen u y Excellen Talen s
in Uni e si y and he P ojec -sponso ed by SRF o ROCS, SEM.
Re e ences
1. Gh. P˘aun, G. Rozenbe g, A. Salomaa, eds.: The Ox o d Handbook o Memb ane Com-
pu ing. Ox o d Uni e si y P ess, 2010.
2. T.Y. Nishida: Memb ane algo i hm wi h b ownian subalgo i hm and gene ic subalgo-
i hm. In e na ional Jou nal o Founda ions o Compu e Science, 18 (2007), 1353–
1360.
3. G.X. Zhang, C.X. Liu, H.N. Rong: Analyzing ada emi e signals wi h memb ane
algo i hms. Ma hema ical and Compu e Modelling, 52 (2010), 1997–2010.
4. G.X. Zhang, J.X. Cheng, M. Gheo ghe: A memb ane-inspi ed app oxima e algo i hm
o a eling salesman p oblems. Romanian Jou nal o In o ma ion Science and Tech-
nology, 14 (2011), 3–19.
5. G.X. Zhang, C.X. Liu, M. Gheo ghe: Di e si y and con e gence analysis o memb ane
algo i hms. P oc. o he Fi h In e na ional Con e ence on Bio-Inspi ed Compu ing:
Theo ies and Applica ion, 2010, 596–603.
6. G.X. Zhang, M. Gheo ghe, C.Z. Wu: A quan um-inspi ed e olu iona y algo i hm
based on P sys ems o Knapsack P oblem. Fundamen a In o ma icae, 87 (2008),
93–116.
7. J.X. Cheng, G.X. Zhang, X.X. Zeng: A no el memb ane algo i hm based on diffe -
en ial e olu ion o nume ical op imiza ion. In e na ional Jou nal o Uncon en ional
Compu ing, 7 (2011), 159–183.
8. G.X. Zhang, M. Gheo ghe, Y.Q. Li: A memb ane algo i hm wi h quan um-inspi ed
subalgo i hms and i s applica ion o image p ocessing. Na u al Compu ing, 2012, DOI:
10.1007/s11047-012-9320-2. (published online)
234 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
conclusion. Once he numbe o “elemen s” in he expe imen is dec easing, mos o
ou me hods o in es iga e p ope ies o hose “elemen s” become ha d/impossible
o desc ibe/in es iga e. Ob iously his s a emen is a he b oad and he e a e
some echniques such as FRET analysis ha look a disc e e e en s/elemen s, bu
we claim ha he majo i y o he cu en bio-molecula echniques do equi e la ge
mul iplici ies o he “elemen ” in es iga ed.
The a o emen ioned ac has o be unde s ood by he esea che looking o
model/simula e cells. I desc ibes he s a e o he esea ch ools in ha a ea. The
modele can help ha pa icula a ea by offe ing be e insigh in o he sub-cellula
p ocesses h ough simula ion and p edic ion. One could immedia ely poin ou ha
since we ha e a “ echnological” p oblem (as s a ed be o e) which is p ecluding us
o gain insigh in o he “disc e e” p ocesses, hen how can one hope o simula e he
sub-cellula mechanisms. The answe is wo- old: (1) cells p o e o espond mos ly
in he same ashion o simila s imuli, meaning ha he inhe en s ochas ici y
o hese sys ems does no “b eak” he esponse pa hways (making he simula ion
om his pe spec i e “easy” as we need o simula e he “impo an ” e en s, no all
he noise associa ed wi h he gene egula ion mechanisms and hei s ochas ici y);
(2) e en i we do no know a mechanism, once a model is buil based on ou bes
knowledge and we see i di e ging om eali y in a specific poin , we know whe e
o s a in es iga ing o o he p ocesses/ eac ions.
The e is also a philosophical mo i a ion o using P sys ems o a cell simu-
la o : P sys ems we e defined o cap u e he compa men alized s uc u e o he
euka yo ic cells, and indeed his compa men aliza ion could p o e one o he bes
ea u es o a cell simula o . Fu he mo e: due o he cu en biomolecula ech-
niques in ol ing la ge mul iplici ies o a species he simula ion echniques in he
a ea ocussed on o dina y diffe en ial equa ions (ODE) as con inuous ma hema ics
bo h has powe ul ools and a e easily implemen ed. Bu we claim ha a con inu-
ous ma hema ics app oach in his a ea o sub-cellula simula ion may no be he
bes app oach as some p ocesses ha e been seen o beha e disc e ely, and in se -
e al pa hways we can see he mul iplici y o some mul ip o ein complexes appea
in e y small numbe s (below 10). In such cases a disc e e simula ion echnique
such as Gillespie’s algo i hm would be p e e able o he simula o s based on ODE
[4].
Inciden ally we ha e also defined a disc e e simula ion echnique in [2] which
was epea edly imp o ed (see e e ences in [5]) and was la ely named NWA wi h
memo y. The mo i a ion behind he NWA algo i hm was simple: we wan ed a dis-
c e e ma hema ics based simula ion echnique ha would be as e han Gillespie’s
algo i hm.
22.1 B ie Desc ip ion o Cu en Cellula Models and Simula o s
In o de o plausibly model he biochemis y o li e, indi idual biochemical in e ac-
ions need o occu asynch onously o e diffe en leng hs o ime. The model elies
on he law o mass ac ion. The law s a es ha eac ion a e is di ec ly p opo -
ional o he numbe o eac an s a ailable in he sys em. In o he wo ds, he ime

F on ie s o Memb ane Compu ing 235
equi ed o execu e a ule in he cell is dependen on he numbe o i s eac ing
species. We no e ha he ule applica ion is no conside ed o be ins an aneous;
he kine ics ha a e gi ing he eac ion speed model he ime equi ed by he
molecules in ol ed in he ule o couple oge he (i he eac ion is o second o de
o highe ) as well as he ime equi ed o he ac ual eac ion o ake place.
The law o mass ac ion gi es us he powe o empo ally desc ibe he e ol ing
configu a ions o ou sys em. To unde s and he asynch ony o ule execu ion, we
need o discuss he kine ic a es pe aining o he law o mass ac ion. The kine ics
o a chemically eac i e sys em a e o en desc ibed as concen a ion-based alues.
This is common o he ypes o expe imen s used o de i e he a es, ypically in-
ol ing eno mous popula ions (millions) o cells. The cells a e o en lysed as a la ge
popula ion, molecules a e measu ed in e ms o ligh in ensi y and da a a e gi en
as concen a ions o species ac oss cell popula ion. These alues can be a e aged
ac oss he cell popula ion, yielding concen a ions pe cell. We ely on hese alues
o fi ou models, bu he alues a e de i ed om en i e cell popula ions ins ead o
indi idual cells. Hence, he in e es ing pheno ypic, biochemical and physiological
cha ac e is ics o indi idual cells can be some imes o e gene alized (o los ) in lieu
o he beha io o he majo i y o he cells in he popula ion.
Some labs employ echniques o measu e single-cell dynamics. Fo example,
in e es ing esul s/models on p53 ha e been epo ed in [7], whe e i is shown ha
indi idual cells unde go no dampened oscilla ions, as epo ed in [1], bu each
indi idual cell ins ead exhibi s a diffe en numbe s o oscilla ions. The a e age
beha io o he cell popula ion appea ed o be dampened, bu indi idual cells did
no beha e his way.
We a e collabo a ing wi h Ma k DeCos e ’s biomedical labo a o y om
Louisiana Tech Uni e si y in o de o s udy single cell da a ia a high-speed imag-
ing sys em. I is ou hope ha u u e collabo a ions will help unlock some o he
sec e s behind Fas-induced apop osis. Rega dless o whe he da a comes om la ge
cell popula ions o single cell dynamics, we, as modele s, mus emain igilan and
build he bes models wi h he da a a ailable o us.
Using he law o mass ac ion and disc e e kine ic cons an s we can define he
Wai ing Time (WT) o a eac ion in he P sys em. The WT is a alue assigned
o each eac ion, signi ying he nex imepoin o a single execu ion o he eac-
ion. As molecula mul iplici ies will change h oughou a simula ion, om one
configu a ion o he nex , so will he WTs o eac ions u ilizing hose molecules.
We used a min-heap o so ing eac ions, whe e he op o he heap is he
eac ion wi h he smalles WT – i.e., he nex eac ion o be execu ed. Howe e , we
need o use nons anda d me hods o main aining he heap, due o he asynch ony
o he ules and he sha ing o eac an s. These nons anda d me hods a e simila
o hose p oposed by Gibson and B uck [3] in hei modifica ion o he Gillespie
algo i hm.
To cla i y, when a ule is applied, mul iple nodes can ha e changes o hei WT,
since he mul iplici ies o pa icula species o he sys em ha e changed. These
species can be sha ed o e mul iple eac ions. Hence, mul iple WT po en ially
236 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
can ail he min-heap p ope y h oughou he ee simul aneously a each new
configu a ion. In o de o handle his, we use heap main enance me hods simila
o hose p oposed by Gibson and B uck [3] in hei modifica ion o he Gillespie
algo i hm.
22.2 Imp o ing he Simula o s
The ollowing “open p oblems” a e mos ly o he simula o de eloped by ou
g oup bu should be ele an o o he simula o s as well.
1. inc ease he s ochas ici y a he le el o he heap by applying a modified
Mon e Ca lo simula ion echnique o he fi s 3 le els o he heap ( he as es 7
eac ions),
2. as e implemen a ion such as using C a he han C++ o Ja a,
3. GPU implemen a ion o he simula o o pa allel simula ions and iden i ying
“decision poin s” in he pa hway; also unning he same model se e al imes could
iden i y he mino i y om he majo i y ( his in o ma ion could be los in an ODE
amewo k o simula ion),
4. bigge and be e models o sub-cellula mechanisms,
5. using Manca’s Log-gain heo y o ga he s oichiome ic da a o be used in
simula ions [6],
6. implemen ing he simula ion amewo k as a plug-in in CoPasi o b oade
dissemina ion and usage.
Acknowledgemen s. The au ho acknowledges suppo om UEFISCDI – PNII-
TE 92/2010.
Re e ences
1. R.L. Ba -O , R. Maya, L.A. Segel, U. Alon, A.J. Le ine, M. O en: Gene a ion o
oscilla ions by he p53-Mdm2 eedback loop: A heo e ical and expe imen al s udy.
P oc. Na l. Acad. Sci., USA, 97 (2000), 11250–11255.
2. S. Che uku, A. P˘aun, F.J. Rome o-Campe o, M.J. P´e ez-Jim´enez, O.H. Iba a: Sim-
ula ing FAS-induced apop osis by using P sys ems. P og ess in Na u al Science, 17
(2007), 424–431.
3. M.A. Gibson, J. B uck: Efficien exac s ochas ic simula ion o chemical sys ems
wi h many species and many channels. Jou nal o Physical Chemis y A, 104 (2000),
1876–1889.
4. D.T. Gillespie: Exac s ochas ic simula ion o coupled chemical Reac ions,” The Jou -
nal o Physical Chemis y, ol. 81, no. 25, 1977, pp. 2340–2361.
5. J. Jack, A. P˘aun: Disc e e modeling o biochemical signaling wi h memo y enhance-
men . LNBI T ansac ions on Compu a ional Sys ems Biology, 5750 (2009), 200–215.
6. V. Manca: The me abolic algo i hm o P sys ems: P inciples and applica ions. The-
o e ical Compu e Science, 404 (2008), 142–155.
7. G. Laha , N. Rosen eld, A. Sigal, N. Ge a-Za o sky, A.J. Le ine, M.B. Elowi z, U.
Alon: Dynamics o he p53-Mdm2 eedback loop in indi idual cells. Na u e Gene ics,
36 (2004), 147–150.
F on ie s o Memb ane Compu ing 237
23 P Sys ems o Compu a ional Sys ems and Syn he ic
Biology
Ma ian Gheo ghe1,2, Vincenzo Manca3,
F ancisco-Jos´e Rome o-Campe o4
1Depa men o Compu e Science, Uni e si y o Pi e¸s i, Romania
2Depa men o Compu e Science, Uni e si y o Sheffield, UK
[email p o ec ed]
3Depa men o Compu e Science, Uni e si y o Ve ona, I aly
[email p o ec ed]
4Resea ch G oup on Na u al Compu ing
Depa men o Compu e Science and A ificial In elligence
Uni e si y o Se illa, Spain
[email p o ec ed]
De e minis ic and s ochas ic P sys em models a e discussed in he con ex o
speci ying ai ly complex biological sys ems; hei usage o sys ems and syn he ic
biology is also p esen ed.
Requi ed No ions: me abolic P sys ems, dynamical in e se p oblem, s ochas ic
P sys ems, Gillespie algo i hm, sys ems biology, syn he ic biology
The app oaches based on P sys ems aiming o p o ide cohe en desc ip ions
o ai ly complex biological sys ems a e ei he de e minis ic o s ochas ic [5]. Two
such a ian s a e discussed below, bu some mo e a ian s o he abo e men ioned
ypes o P sys ems a e a ailable in he cu en li e a u e, see [15] and Sec ions 21
and 22 o his pape .
Me abolic P sys ems (MP sys ems o sho ) we e in oduced in 2004 as a pa -
icula kind o P sys ems de ised o modeling me abolic p ocesses [7]. Thei main
goal consis s in sol ing dynamical in e se p oblems (DIPs) by means o disc e e
sys ems. A gene al algo i hm, called Log-Gain S oichiome ic S epwise Reg ession
(LGSS), p o iding MP solu ions o DIPs was ob ained, in a sys ema ic way, by
in eg a ing fini e diffe ence ecu en equa ions, leas squa e me hod, s epwise e-
g ession, and ela ed Fishe es s, wi hin a sui able linea algeb a amewo k whe e
solu ions can be exp essed as o dina y and enso p oduc s among ma ices [11].
A MATLAB implemen a ion o LGSS was de eloped by Luca Ma che i [12].
Many success ul applica ions o MP heo y o biological dynamics we e de el-
oped, s a ing om classical examples (Lo ka-Vol e a, B ussela o , Mi o ic Oscil-
la o ) [10]. P esen ly, he wo main applica ions unde in es iga ion conce n he
insulin-glucose dynamics in diabe es pa hologies and gene ic exp ession in a kind o
b eas cance (in coope a ion wi h endoc inologis s and clinicians in I aly, Ve ona
and in USA, De oi ). A syn he ic desc ip ion and e e ences is gi en by Vincenzo
Manca in [8, 9].
238 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
S ochas ic P sys ems, SP sys em o sho , a e ule-based disc e e and s ochas-
ic mul icompa men al sys ems used as abs ac s uc u es o model s ochas ic
cellula sys ems [14]. The key diffe ence be ween he o iginal P sys ems and SP
sys ems consis s in a s ochas ic cons an ha is specifically associa ed wi h each
ule. This cons an is used o de e mine in a specific s a e o configu a ion o he
sys em he p obabili y o applying he co esponding ule and he ime elapsed
be ween ule applica ions acco ding o Gillespie’s s ochas ic simula ion algo i hm
[6].
SP sys ems allow he inc emen al and pa simonious design o models by p o-
iding modele s wi h he ea u e o modula i y explici ly [4]. A P sys em module
consis s o a fini e se o ew i ing ules ha may con ain some ee a iables in
hei objec s, labels and s ochas ic cons an s. Modules can be a anged in lib a ies
so hey can be eused o define he ew i ing ules o diffe en models. In his e-
spec , modules ac like mac os ha ge expanded once he co esponding module
a iables a e ins an ia ed wi h specific molecula species names, nume ical alues
o he s ochas ic cons an s and compa men names.
A a ian o SP sys ems, la ice popula ion P sys ems [18], allow modele s o
ep esen mul i-cellula sys ems wi h specific geome ies by dis ibu ing copies o
gi en indi idual s ochas ic P sys ems o e he poin s o a fini e geome ical la ice.
SP sys ems ha e been implemen ed in he so wa e ool o he specifica ion,
simula ion, analysis and op imiza ion o sys ems and syn he ic biology models,
In obio ics wo kbench [3].
These sys ems ha e been used o model signal ansduc ion pa hways [13, 1],
bac e ial gene egula ion [17], bac e ial popula ions [16], me apopula ions [2] and
syn he ic biology p oblems [19].
Memb ane compu ing has made e y significan con ibu ions in ce ain a eas
o compu e science and has p oduced some impac wi h espec o a numbe o
applica ions. I emains a challenge o show how i copes wi h complex applica-
ions, especially in sys ems and syn he ic biology. Some o hese challenges a e
lis ed below:
•iden i y mo e complex sys ems o be specified by one o he a ian s o P
sys ems desc ibed abo e o p esen ed in [15];
•ex end he cu en a ian s wi h addi ional ea u es in o de o cope wi h mo e
complex applica ions;
•c ea e a eposi o y o illus a i e biological case s udies;
•de elop addi ional complemen a y app oaches ha help analyzing biological
sys ems – da a sensi i i y analysis, p ope y da a ex ac ion and e ifica ion,
hie a chies o languages allowing o map P sys em specifica ions in o bio-
chemical eac ions;
•implemen adequa e ools exploi ing he la es echnologies and c ea e bench-
ma k p oblems o assess hem.
F on ie s o Memb ane Compu ing 239
Acknowledgemen . M.G.’s wo k was pa ially suppo ed by p ojec MuVe , Ro-
manian Na ional Au ho i y o Scien ific Resea ch (CNCS, UEFISCDI) g an num-
be PN-II-ID-PCE-2011-3-0688.
Re e ences
1. D. Besozzi, P Cazzaniga, S. Cocolo, G. Mau i, D. Pescini: Modelling diffusion in a
signal ansduc ion pa hway: he use o i ual olumes in P sys ems. In . J. Found.
Compu . Sci., 22 (2011), 89–96.
2. D. Besozzi, P Cazzaniga, D. Pescini, G. Mau i: Modelling me apopula ions wi h
s ochas ic memb ane sys ems. BioSys ems, 91 (2008), 499–514.
3. J. Blakes, J. Twyc oss, F.J. Rome o-Campe o, N. K asnogo : The In obio ics Wo k-
bench: an in eg a ed in silico modelling pla o m o Sys ems and Syn he ic Biology.
Bioin o ma ics, 27 (2011), 3323–3324.
4. H. Cao, F.J. Rome o-Campe o, S. Heeb, M. C´ama a, N. K asnogo : E ol ing cell
models o sys ems and syn he ic biology. Sys . Syn h. Biol., 4 (2010), 55–84
5. M. Gheo ghe, V. Manca, F.J. Rome o-Campe o: De e minis ic and s ochas ic P sys-
ems o modelling cellula p ocesses. Na u al Compu ing, 9 (2010), 457–473.
6. D.T. Gillespie: S ochas ic simula ion o chemical kine ics. Annual Re iew o Physical
Chemis y, 58 (2007), 35–55.
7. V. Manca: The me abolic algo i hm o P sys ems: P inciples and applica-
ions.Theo e ical Compu e Science, 404 (2008), 142–155.
8. V. Manca: Me abolic P sys ems.Schola pedia, 6 (2010), 9273.
9. V. Manca: Fundamen als o me abolic P sys ems. Chap e 6 in [15], 475–498.
10. V. Manca L. Bianco, F. Fon ana: E olu ions and oscilla ions o P sys ems: Theo-
e ical conside a ions and applica ion o biological phenomena. P oc. WMC 2004,
Milan, I aly, June 2004, LNCS 3365, Sp inge , 2005, 63–84.
11. V. Manca, L. Ma che i: Sol ing dynamical in e se p oblems by means o me abolic
P sys ems. BioSys ems, o appea . DOI:10.1016/j.biosys ems.2011.12.006.
12. L. Ma che i, V. Manca: A me hodology based on MP heo y o gene exp es-
sion analysis. P oc. CMC 2011, Fon ainebleau, F ance, Augus 2011, LNCS 7184,
Sp inge , 2012, 300–313.
13. A. P˘aun, M.J. P´e ez-Jim´enez, F.J. Rome o-Campe o: Modeling signal ansduc ion
using P sys ems. P oc. WMC 2006, Leiden, The Ne he lands, July 2006, LNCS 4361,
Sp inge , 2006, 100–122.
14. Gh. P˘aun, F.J. Rome o-Campe o: Memb ane compu ing as a modeling amewo k:
cellula sys ems case s udies. P oc. Fo mal Me hods o Compu a ional Biology, 8 h
In e n. School, Be ino o, I aly, June 2008 (M. Be na do e al, eds.), LNCS 5012,
Sp inge , 2008, 168–214.
15. Gh. P˘aun, G. Rozenbe g, A. Salomaa, eds.: The Ox o d Handbook o Memb ane
Compu ing. Ox o d Uni . P ess, 2010.
16. F.J. Rome o-Campe o, M.J. P´e ez-Jim´enez: A model o he quo um sensing sys em
in Vib io fische i using P sys ems. A i icial Li e, 14 (2008), 95–109.
17. F.J. Rome o-Campe o, M.J. P´e ez-Jim´enez: Modelling gene exp ession con ol using
P sys ems: The Lac Ope on, a case s udy. BioSys ems, 91 (2008), 438–457.
18. F.J. Rome o-Campe o, J. Twyc oss, M. C´ama a, M. Benne , M. Gheo ghe, N.
K asnogo : Modula assembly o cell sys ems biology models using P sys ems. In .
J. Found. Compu . Sci., 20 (2009), 427–442.

240 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
19. J. Smaldon, F.J. Rome o-Campe o, F. Fe n´andez T illo, M. Gheo ghe, C. Alexande ,
N. K asnogo : A compu a ional s udy o liposome logic: owa ds cellula compu ing
om he bo om up. Sys . Syn h. Biol., 4 (2010), 157–179.
24 Biologically Plausible Applica ions o SN P Sys ems o
an Explana ion o B ain Cogni i e Func ions
Adam Ob ulowicz
Ins i u e o Ma hema ics, Polish Academy o Sciences, Wa saw, Poland
[email p o ec ed]
Some conjec u es abou he possibili y o using SN P sys ems and ex ension
o hem o modeling ea u es o he b ain (such as lea ning, modula i y) a e
o mula ed.
Requi ed No ions: spiking neu on, SN P sys em, lea ning
The (hie a chical) clus e ing (scene segmen a ion in pa icula ) and binding
( ea u e in eg a ion) p oblem solu ion in co ical neu al ne wo ks oge he wi h
co ical subne wo ks ealizing Radial Basic Func ions (b iefly RBFs) ep esen ,
among o he s, he cogni i e unc ioning o b ain. Recen ly, a ious ne wo k mod-
els o clus e ing, binding p oblem solu ion, and ealiza ion o RBFs in co ical
ne wo ks ha e been p oposed, whe e spiking neu al ne wo ks a e he mos biolog-
ically plausible models, see [16], [17], [2], [3], [12], [14], [15], and [11] o a e iew.
The main common ea u e o hese models is Hebbian lea ning which p o ides
hei biological e idence. On he o he hand, a ans o ma ion o an idea o Heb-
bian lea ning om a amewo k o spiking neu al ne wo ks o a amewo k o SN
P sys ems (c . [10]) has been p oposed in [8]. Thus, one o mula es he ollowing
ques ion:
Do SN P sys ems p o ide biologically plausible ma hema ical models o
b ain cogni i e unc ions?
We app oach he ques ion and an answe o i by he ollowing discussion o
conjec u es and se ing open p oblems.
Pape s [5], [9] con ain p omising applica ions o SN P sys ems o sol ing opic
p oblems ela ed o some cogni i e b ain unc ions. Bu biological e idence o hese
applica ions seems p oblema ic because Hebbian lea ning p ocedu es app oach is
no conside ed o hem.
On he o he hand, he Hebbian lea ning modeled by SN P sys ems wi h only
inpu neu ons and one ou pu neu on p esen ed in [8] and solu ion o XOR p oblem
by spiking neu al ne wo ks equipped wi h a Hebbian lea ning p ocedu e and wi h
F on ie s o Memb ane Compu ing 241
only h ee inpu neu ons and one ou pu neu on desc ibed in [4] gi es ise o he
ollowing conjec u e:
Conjec u e 1. The e exis s a lea ning p oblem, unde s ood as in [8], whose ou pu
is an SN P sys em sol ing XOR p oblem.
I we compa e p ecise iming o spikes app oach o spiking neu al ne wo ks o
he numbe o spikes app oach o SN P sys ems, hen he la e seems coa se and
hence less biologically plausible han he spiking neu al ne wo k app oach.
On he o he hand, he p ecise iming o spikes app oach o spiking neu al
ne wo ks is less biologically plausible han p obabilis ic spiking neu al ne wo ks
because a ele an amoun o noise is con ained in he beha io o neu ons (c . [7]).
The e o e i is wo h o ini ia e a esea ch o p obabilis ic SN P sys ems.
The iew ha human mind is “massi ely modula ” (c . [6], [13]) a gued by
massi ely pa allel unc ioning o b ain neu al ne wo k modules, gi es ise o a
ques ion o app oaching hese massi e modula i y and massi e pa allelism o mind
and b ain by applica ion o a concep o a ne wo k o communica ing SN P sys-
ems equipped wi h Hebbian lea ning p ocedu es, espec i ely. The SN P sys ems
cons i u ing ha ne wo k could co espond o b ain ne wo k modules ealizing
simul aneously a ious cogni i e unc ions, espec i ely.
On he o he hand, since SN P sys ems seem mo e coa se wi h espec o an
app oach o ime han spiking neu al ne wo ks wi h p ecise iming o spikes, like,
e.g., in [2], we p opose he ollowing conjec u e.
Conjec u e 2. A biologically plausible modula i y o b ain could be ep esen ed
(modeled)by he ollowing hyb id cons uc s:
1. a wo-le el cons uc o a spiking supe -neu al P sys em which is an SN P sys-
em whose neu ons a e supe neu ons, i.e., mul i-laye spiking neu al ne wo ks
wi h a p ecise iming o spikes like, e.g., in [2],
2. a h ee-le el cons uc o a spiking sub-supe -neu al P sys em which is a spik-
ing supe -neu al P sys em as abo e, whe e he neu ons o supe neu ons a e
P sys ems app oaching neu ons as cells which p oduce and anspo copies o
molecules be ween elec ically cha ged memb anes.
The cons uc in 1) gi es ise o mul i-laye spiking ne wo ks which could lea n
hemsel es like in [2] hei modula s uc u e o spiking supe -neu al P sys ems
and hence which could explain eme gence o cogni i e capabili ies o b ain.
I is wo h o discuss he abo e cons uc s wi h ega d o he possibili y o hei
molecula implemen a ion which is sugges ed by ecen findings ou lined in [1].
Re e ences
1. A. Bandyopadhyay, D. Fuji a, R. Pa i: A chi ec u e o a massi ely pa allel p ocess-
ing nano-b ain ope a ing 100 billion molecula neu ons simul aneously. In e na ional
Jou nal o Nano echnology and Molecula Compu a ion, 1 (2009), 50–80.
242 M. Gheo ghe, Gh. P˘aun, M.J. P´e ez-Jim´enez, eds.
2. S.M. Boh e: Spiking Neu al Ne wo ks. P o esso sch i , Leiden Uni e si y, 2003.
3. O. Booij: Tempo al Pa e n Classi ica ion using Spiking Neu al Ne wo ks. M.Sc. The-
sis, Ams e dam Uni e si y 2004.
4. O. Booij, Hieu a Nguyen: A g adien descen ule o spiking neu ons emi ing
mul iple spikes. Applica ions o Spiking Neu al Ne wo ks (S.M. Boh e, J.N. Kok,
eds.), In o ma ion P ocessing Le e s, Ams e dam, 2005.
5. R. Ce e chi, I.A. Tomescu: Spiking neu al P sys ems–a na u al model o so ing
ne wo ks. P oc. Six h B ains o ming Week on Memb ane Compu ing (D. Diaz-Pe nil
e al., eds.), Se illa, Feb ua y 4–8, 2008, RGNC Repo 01/2008, Fenix Edi o a,
Se illa, 2008, 93–105.
6. D. Gea y: The O igin o Mind: E olu ion o B ain, Cogni ion, and Gene al In elli-
gence. Ame ican Psychological Associa ion 2005.
7. W. Ge s ne : Popula ion dynamics o spiking neu ons: Fas ansien s, asynch onous
s a es, and locking. Neu al Compu a ion, 12 (2000), 43–89.
8. M.A. Gu i´e ez-Na anjo, M.J. P´e ez-Jim´enez: A spiking neu al P sys ems based model
o Hebbian lea ning. P oc. 9 h Wo kshop on Memb ane Compu ing (P. F isco e al.,
eds.), Edinbu gh, July 28–31, 2008, 189–207.
9. M. Ionescu, D. Sbu lan: Some applica ions o spiking neu al P sys ems. P oc. 8 h
Wo kshop on Memb ane Compu ing (Ele he akis e al., eds.), Thessaloniki, June
25–28, 2007, 383–394.
10. M. Ionescu, Gh. P˘aun, T. Yokomo i: Spiking neu al P sys ems. Fund. In o m.,
71 (2006), 279–308.
11. A. Kasi´nski, F. Ponulak: Compa ison o supe ised lea ning me hods o spike ime
coding in spiking neu al ne wo ks. In . J. Appl. Ma h. Compu . Sci., 16 (2006), 101–
113.
12. A. Knoblauch, G. Palm: Scene segmen a ion by spike synch oniza ion in ecip ocally
connec ed isual a eas. II: Global assemblies and synch oniza ion on la ge space and
ime scales. Biol. Cybe n., 87 (2002), 168–184.
13. K. MacDonald, D. Chiappe: Re iew o [6] in Human E hology Bulle in, 21 (2006),
14–18.
14. B. Me ah, A. Benye ou, O. Lezo ay, W. Qingxiang: Image clus e ing wi h spiking
neu on ne wo k. Wo ld Cong ess on Compu a ional In elligence, In e na ional Join
Con e ence on Neu al Ne wo ks, Hong-Kong, 2008.
15. S.C. Moo e: Back-p opaga ion in Spiking Neu al Ne wo ks. M.Sc. Thesis, Uni e si y
o Ba h 2002, h p://www.simonch is ianmoo e.co.uk/Thesis4.h ml.
16. T. Na schl¨age , B. Ru : Spa ial and empo al pa e n analysis ia spiking neu ons.
Ne wo k: Comp. Neu al Sys ems, 9 (1998), 319–332.
17. B. Ru : Compu ing and Lea ning wi h Spiking Neu ons–Theo y and Simula ion. Doc-
o al Thesis, Technische Uni e si ¨a G az, 1998.
F on ie s o Memb ane Compu ing 243
25 Compu e Vision
Daniel D´ıaz-Pe nil1, Miguel A. Gu i´e ez-Na anjo2
1CATAM Resea ch G oup, Dep . o Applied Ma hema ics I
Uni e si y o Se illa, Spain
[email p o ec ed]
2Resea ch G oup on Na u al Compu ing, Dep . o Compu e Science and AI
Uni e si y o Se illa, Spain
[email p o ec ed]
Some possibili ies o employ MC echniques in compu e ision (especially in
h esholding, smoo hing, homology heo y) a e discussed.
Requi ed No ions: a ay g amma , a ay- ew i ing P sys em, cell and issue P
sys ems
Compu e ision is p obably one o he challenges o compu e scien is s in he
nex yea s. F om a biological poin o iew, ision is an ex emely complex p ocess
in ol ing he ans o ma ion o he ligh ene gy in o a signal which lea es he eye
by way o he op ic ne e and a i es o he b ain, whe e i is in e p e ed. F om a
compu a ional poin o iew, a digi al image is a unc ion om a wo dimensional
su ace which maps each poin o m he su ace o a se o ea u es as b igh o
colo .
In MC, he e is a la ge adi ion in handling in o ma ion s uc u ed as wo
dimensional objec s (see, e.g., [2, 3, 9, 16]). The main mo i a ion o hese s udies
is o b ing oge he P sys ems and pic u e g amma s. F om a echnical poin o
iew, a ays a e wo-dimensional objec s placed inside he memb anes as s ings
a e one-dimensional objec s in he model o P sys ems wi h s ing objec s [13].
In [3], he model o a ay- ew i ing P sys ems was p esen ed on he basis o
he ansi ion P sys ems: Rules a e o ype A → B( a ) whe e Ais he a ay o be
ew i en, Bis he new one, and a ∈ {he e, in, ou }indica es he place o he
pic u e a e he subs i u ion has been made.
Recen ly, a new esea ch line has been open by applying well-known MC ech-
niques o sol ing p oblems om digi al image y. Fo example, segmen a ion is he
p ocess o assigning a label o e e y pixel in an image such ha pixels wi h he
same label sha e ce ain isual cha ac e is ics. Segmen a ion has shown i s u il-
i y, o example, in bo de ing umo s and o he pa hologies o compu e -guided
su ge y. In [5, 8, 10, 11] we can find se e al app oaches o his p oblem wi h MC
echniques. O he p oblems, as h esholding [4] o smoo hing [18] ha e also been
conside ed in he amewo k o MC. Special a en ion dese es [14], whe e he sym-
me ic dynamic p og amming s e eo (SDPS) algo i hm [15] o s e eo ma ching was
implemen ed by using simple P modules wi h duplex channels.
A diffe en app oach o compu e ision can also be ob ained om compu a-
ional opology. In pa icula , algeb aic opology p o ides echniques and algo-
i hms o handling digi al images om a opological poin o iew. Recen ly, he