Inpu -D i en Tissue P Au oma a
A iom Alhazo 1, Rudol F eund2, Se giu I ano 3,
Ma ion Oswald2, and Se gey Ve lan4
1Ins i u e o Ma hema ics and Compu e Science
Academiei 5, Chişinău, MD-2028, Moldo a
[email p o ec ed]
2Facul y o In o ma ics, TU Wien
Fa o i ens aße 9–11, 1040 Vienna, Aus ia
{ udi,ma ion}@emcc.a
3IBISC, Uni e si é É y, Uni e si é Pa is-Saclay
23 Boule a d de F ance, 91025, É y, F ance
[email p o ec ed]
4Labo a oi e d’Algo i hmique, Complexi é e Logique,
Uni e si é Pa is Es C é eil,
61 A enue du Géné al de Gaulle, 94010 C é eil, F ance
[email p o ec ed]
Summa y. We in oduce se e al a ian s o inpu -d i en issue P au oma a whe e he
ules o be applied only depend on he inpu symbol. Bo h s ings and mul ise s a e
conside ed as inpu objec s; he s ings a e ei he ead om an inpu ape o de ined
by he sequence o symbols aken in, and he mul ise s a e gi en in an inpu cell a he
beginning o a compu a ion, enclosed in a esicle. Addi ional symbols gene a ed du ing a
compu a ion a e s o ed in his esicle, oo. An inpu is accep ed when he esicle eaches a
inal cell and i is emp y. The compu a ional powe o some a ian s o inpu -d i en issue
P au oma a is illus a ed by examples and compa ed wi h he powe o he inpu -d i en
a ian s o o he au oma a as egis e machines and coun e au oma a.
1 In oduc ion
In he basic model o memb ane sys ems as in oduced a he end o he las
cen u y by Gheo ghe Păun, e.g., see [9] and [30], he memb anes a e o ganized
in a hie a chical memb ane s uc u e (i.e., he connec ion s uc u e be ween he
compa men s/ egions wi hin he memb anes being ep esen able as a ee), and
he mul ise s o objec s in he memb ane egions e ol e in a maximally pa allel
way, wi h he esul ing objec s also being able o pass h ough he su ounding
memb ane o he pa en memb ane egion o o en e an inne memb ane. Many
a ian s o memb ane sys ems, o ob ious easons mos ly called P sys ems, ha e
40 A. Alhazo e al.
been in es iga ed du ing nea ly wo decades, mos o hem being compu a ionally
comple e, i.e., being able o simula e he compu a ions o egis e machines. I an
a bi a y g aph is used as he connec ion s uc u e be ween he cells/memb anes,
he sys ems a e called issue P sys ems, see [21].
Ins ead o mul ise s o plain symbols coming om a ini e alphabe , P sys ems
qui e o en ope a e on mo e complex objec s (e.g., s ings, a ays), oo. A com-
p ehensi e o e iew o di e en a ian s o ( issue) P sys ems and hei exp essi e
powe is gi en in he handbook which appea ed in 2010, see [31]. Fo a sho iew
on he s a e o he a on he domain, we e e he eade o he P sys ems web-
si e [34] as well as o he Bulle in se ies o he In e na ional Memb ane Compu ing
Socie y [33].
The no ion and concep o inpu -d i en push-down au oma a goes back o
he seminal pape [22] as well as he pape s [6] and [10] imp o ing he complexi y
measu es shown in [22]. The main idea o inpu -d i en push-down au oma a is ha
he inpu le e s uniquely de e mine whe he he au oma on pushes a symbol, pops
a symbol, o lea es he pushdown unchanged. Inpu -d i en push-down au oma a
ha e been edisco e ed a he beginning o his cen u y unde he name o isibly
pushdown au oma a, see [3] and [4]. Since hen, a ian s o inpu -d i en push-
down au oma a ha e gained g owing in e es , especially because closu e p ope ies
and decidable ques ions o he language classes de ined by hese de ices u n ou
o be simila o hose o egula languages. Se e al new a ian s o inpu -d i en
au oma a ha e been de eloped, o example, using s acks o queues, see [5], [19],
and [20]. Fo complexi y issues o inpu -d i en push-down au oma a, he eade is
e e ed o [24, 25, 26, 27].
The so-called poin mu a ions, i.e., inse ion,dele ion, and subs i u ion, which
mean inse ing o dele ing one symbol o eplacing one symbol by ano he one in
a s ing o mul ise a e e y simple biologically mo i a ed ope a ions. Fo exam-
ple, on s ings g aph-con olled inse ion-dele ion sys ems ha e been in es iga ed
in [13], and P sys ems using hese ope a ions a he le o igh end o s ing
objec s we e in oduced in [16], whe e also a sho his o y o using hese poin
mu a ions in o mal language heo y can be ound.
The ope a ions o inse ion and dele ion in mul ise s show a close ela ion
wi h he inc emen and dec emen ins uc ions in egis e machines. The powe o
changing s a es in connec ion wi h he inc emen and dec emen ins uc ions hen
can be mimicked by mo ing he whole mul ise ep esen ing he con igu a ion o a
egis e machine om one cell o ano he one in he co esponding issue sys em
a e he applica ion o an inse ion o dele ion ule. Ye usually mo ing he whole
mul ise o objec s in a cell o ano he one, besides maximal pa allelism, equi es
a ge ag eemen be ween all applied ules, i.e., ha all esul s a e mo ed o he
same a ge cell, e.g., see [15].
A di e en app oach has been in oduced in [2]: in o de o gua an ee ha he
whole mul ise is mo ed e en i only one poin mu a ion is applied, he mul ise
Inpu -D i en Tissue P Au oma a 41
is enclosed in a esicle, and his esicle is mo ed om one cell o ano he one
as a whole, no ma e i a ule has been applied o no . Requi ing ha one ule
has o be applied in e e y de i a ion s ep, a cha ac e iza ion o he amily o
se s o ( ec o s o ) na u al numbe s de ined by pa ially blind egis e machines,
which i sel co esponds wi h he amily o se s o ( ec o s o ) na u al numbe s
ob ained as numbe (Pa ikh) se s o s ing languages gene a ed by g aph-con olled
o ma ix g amma s wi hou appea ance checking, is ob ained.
The idea o using esicles o mul ise s has al eady been used in a ian s o P
sys ems using he ope a ions d ip and ma e, co esponding wi h he ope a ions
cu and pas e well-known om he a ea o DNA compu ing, see [14]. Ye in ha
case, always wo esicles (one o hem possibly an axiom a ailable in an unbounded
numbe ) ha e o in e ac . In he model as in oduced in [2] and also o be adap ed
in his pape , he ules a e always applied o he same esicle. The poin mu a ions,
i.e., inse ion,dele ion, and subs i u ion, well-known om biology as ope a ions
on DNA, ha e also widely been used in he a ian s o ne wo ks o e olu iona y
p ocesso s (NEPs), which consis o cells (p ocesso s) each o hem allowing o
speci ic ope a ions on s ings, and in each de i a ion s ep, a e he applica ion o a
ule, allow he esul ing s ing o be sen o ano he cell p o ided speci ic condi ions
( o example, andom con ex ou pu and inpu il e s). A sho o e iew on NEPs
is gi en in [2], oo.
In his pape , we now in oduce inpu -d i en issue P au oma a whe e he
ules o be applied only depend on he inpu symbol. Taking s ings as inpu
objec s, hese a e ei he ead om an inpu ape o de ined by he sequence o
symbols aken in, and as a kind o addi ional s o age we use a mul ise o di e en
symbols enclosed in a esicle which mo es om one cell o he issue P sys em o
ano he one depending on he inpu symbol; he inpu symbol a he same ime
also de e mines whe he (one o mo e) symbols a e added o he mul ise in he
esicle o emo ed om he e. The gi en inpu is accep ed i he whole inpu has
been ead and he esicle has eached a inal cell and is emp y a his momen .
When using mul ise s as inpu objec s, hese a e enclosed in he esicle in he
inpu cell a he beginning o a compu a ion, which esicle hen will also ca y
he addi ional symbols. The gi en inpu mul ise is accep ed i no inpu symbols
a e p esen any mo e and he esicle has eached a inal cell and is emp y a his
momen .
As ules ope a ing on he mul ise enclosed in he esicle when ead-
ing/consuming an inpu symbol we use inse ion, dele ion, and subs i u ion o
mul ise s, applied in he sequen ial de i a ion mode. As es ic ed a ian s, we
conside sys ems wi hou allowing subs i u ion o mul ise s and sys ems only al-
lowing symbols o be inse ed o dele ed (o subs i u ed) as i is common when
using poin mu a ion ules.
Mul ise au oma a ha e al eady been conside ed in [7], whe e models o ini e
au oma a, linea bounded au oma a, and Tu ing machines wo king on mul ise s
a e discussed. When dealing wi h mul ise s only, he issue P au oma a conside ed
42 A. Alhazo e al.
in his pape can be seen as one o he a ian s o mul ise pushdown au oma a as
in es iga ed in [18], whe e no checking o he emp iness o he mul ise memo y
du ing he compu a ion is possible. Va ious lemmas p o ed he e hen can imme-
dia ely be adap ed o ou model. Mo eo e , also he inpu -d i en a ian s can be
de ined in a simila manne , al hough inpu -d i en mul ise pushdown au oma a
ha e no ye been conside ed in ha pape .
We should also like o men ion ha he con ol gi en by he unde lying com-
munica ion s uc u e o he issue P sys em could also be in e p e ed as ha ing a
P sys em wi h only one memb ane bu using s a es ins ead. Fo a discussion on
how o use and in e p e ea u es o ( issue) P sys ems as s a es we e e o [1],
whe e also an example only using he poin mu a ion ules inse ion and dele ion
is gi en. Mo eo e , we will also conside ano he al e na i e model e y common
in he P sys ems a ea, i.e., P sys ems wi h an ipo and sympo ules, which we e
in oduced in [29]; o an o e iew, we e e o [31], Chap e 5. One-memb ane P
sys ems using an ipo ules in a sequen ial manne and wi h speci ic es ic ions
on he ules hen a e an adequa e model o (inpu -d i en) P au oma a, ye he
es ic ions a e less isible han in he model o inpu -d i en issue P au oma a.
On he o he hand, when dealing wi h s ings ins ead o mul ise s, he way how o
ead o de ine he inpu s ing in P sys ems wi h an ipo ules has al eady been
in es iga ed ho oughly, e.g., see [8], [28], and [11] o an o e iew.
The es o he pape now is s uc u ed as ollows: In Sec ion 2 we ecall some
well-known de ini ions om o mal language heo y. The main de ini ions o he
model o (inpu -d i en) issue P au oma a as well as i s a ian s o be conside ed
in his pape a e gi en in Sec ion 3, and he e we also p esen he de ini ion o he
al e na i e model o (inpu -d i en) one-memb ane P au oma a wi h ( es ic ed)
an ipo ules; mo eo e we also gi e some i s examples and esul s. Fu he
illus a i e examples and some mo e esul s, especially o inpu -d i en issue P
au oma a a e exhibi ed in Sec ion 4. As uppe bound o he amily o se s o
ec o s o na u al numbe s accep ed by inpu -d i en issue P au oma a we ge he
amily o se s o ec o s o na u al numbe s gene a ed by pa ially blind egis e
machines, and as uppe bound o he amily o se s o s ings accep ed by inpu -
d i en issue P au oma a we ge he amily o se s o s ings accep ed by pa ially
blind coun e au oma a. A summa y o he esul s ob ained in his pape and an
ou look o u u e esea ch a e p esen ed in Sec ion 5.
2 P e equisi es
We s a by ecalling some basic no ions o o mal language heo y. An alphabe is
a non-emp y ini e se . A ini e sequence o symbols om an alphabe Vis called
as ing o e V. The se o all s ings o e Vis deno ed by V∗; he emp y s ing
is deno ed by λ; mo eo e , we de ine V+=V∗ {λ}. The leng h o a s ing xis
deno ed by |x|, and by |x|awe deno e he numbe o occu ences o a le e ain a
s ing x.
Inpu -D i en Tissue P Au oma a 43
Amul ise Mwi h unde lying se Ais a pai (A, )whe e :A→Nis a map-
ping, wi h Ndeno ing he se o na u al numbe s (non-nega i e in ege s). I M=
(A, )is a mul ise hen i s suppo is de ined as supp(M) = {x∈A| (x)>0}. A
mul ise is emp y ( espec i ely ini e) i i s suppo is he emp y se ( espec i ely
a ini e se ). I M= (A, )is a ini e mul ise o e Aand supp(M) = {a1, . . . , ak},
hen i can also be ep esen ed by he s ing a (a1)
1. . . a (ak)
ko e he alphabe
{a1, . . . , ak}( he co esponding ec o ( (a1), . . . , (ak)) o na u al numbe s is
called Pa ikh ec o o he s ing a (a1)
1. . . a (ak)
k), and, mo eo e , all pe mu a-
ions o his s ing p ecisely iden i y he same mul ise M( hey ha e he same
Pa ikh ec o ). The se o all mul ise s o e he alphabe Vis deno ed by V◦.
The amily o all ecu si ely enume able se s o s ings is deno ed by RE, he
co esponding amily o ecu si ely enume able se s o Pa ikh ec o s is deno ed
by P sRE. Fo mo e de ails o o mal language heo y he eade is e e ed o he
monog aphs and handbooks in his a ea, such as [32].
2.1 Inse ion, Dele ion, and Subs i u ion
Fo an alphabe V, le a→bbe a ew i ing ule wi h a, b ∈V∪ {λ}, and ab 6=λ;
we call such a ule a subs i u ion ule i bo h aand ba e di e en om λand we
also w i e S(a, b); such a ule is called a dele ion ule i a6=λand b=λ, and i
is also w i en as D(a);a→bis called an inse ion ule i a=λand b6=λ, and
we also w i e I(b). The se s o all inse ion ules, dele ion ules, and subs i u ion
ules o e an alphabe Va e deno ed by InsV,DelV, and SubV, espec i ely.
Whe eas an inse ion ule is always applicable, he applicabili y o a dele ion and
a subs i u ion ule depends on he p esence o he symbol a. We ema k ha
inse ion ules, dele ion ules, and subs i u ion ules can be applied o s ings
as well as o mul ise s. Whe eas in he s ing case, he posi ion o he inse ed,
dele ed, and subs i u ed symbol ma e s, in he case o a mul ise his only means
inc emen ing he numbe o symbols b, dec emen ing he numbe o symbols a,
o dec emen ing he numbe o symbols aand a he same ime inc emen ing he
numbe o symbols b.
These ypes o ules and he co esponding no a ions can be ex ended by al-
lowing mo e han one symbol on he le -hand and/o he igh -hand side, i.e.,
a, b ∈V∗, and ab 6=λ. The co esponding se s o all ex ended inse ion ules,
dele ion ules, and subs i u ion ules o e an alphabe Va e deno ed by Ins∗
V,
Del∗
V, and Sub∗
V, espec i ely.
2.2 Regis e Machines
Regis e machines a e well-known uni e sal de ices o compu ing (gene a ing o
accep ing) se s o ec o s o na u al numbe s.
De ini ion 1. A egis e machine is a cons uc M= (m, B, I, h, P)whe e
•mis he numbe o egis e s,

44 A. Alhazo e al.
•Bis a se o labels bijec i ely labeling he ins uc ions in he se P,
•I⊆Bis he se o ini ial labels, and
•h∈Bis he inal label.
The labeled ins uc ions o Min Pcan be o he ollowing o ms:
•p: (ADD ( ), K), wi h p∈B {lh},K⊆B,1≤ ≤m.
Inc ease he alue o egis e by one, and non-de e minis ically jump o one
o he ins uc ions in K.
•p: (SUB ( ), K, F), wi h p∈B {lh},K, F ⊆B,1≤ ≤m.
I he alue o egis e is no ze o hen dec ease he alue o egis e by one
(dec emen case) and jump o one o he ins uc ions in K, o he wise jump o
one o he ins uc ions in F(ze o- es case).
•h:HALT.
S op he execu ion o he egis e machine.
Acon igu a ion o a egis e machine is desc ibed by he con en s o each eg-
is e and by he alue o he cu en label, which indica es he nex ins uc ion o
be execu ed.
In he accep ing case, a compu a ion s a s wi h he inpu o a k- ec o o
na u al numbe s in i s i s k egis e s and by execu ing one o he ini ial ins uc-
ions o P(labeled wi h l∈I); i e mina es wi h eaching he HALT-ins uc ion.
Wi hou loss o gene ali y, we may assume all egis e s o be emp y a he end o
he compu a ion.
By L(RM)we deno e he amily o se s o ec o s o na u al numbe s accep ed
by egis e machines. I is olklo e (e.g., see [23]) ha PsRE =L(RM).
Pa ially blind egis e machines
In he case when a egis e machine canno check whe he a egis e is emp y
we say ha i is pa ially blind: he egis e s a e inc eased and dec eased by one
as usual, bu i he machine ies o sub ac om an emp y egis e , hen he
compu a ion abo s wi hou p oducing any esul ( ha is we may say ha he
sub ac ins uc ions a e o he o m p: (SUB ( ), K, abo ); ins ead, we simply
will w i e p: (SUB ( ), K).
Mo eo e , accep ance now by de ini ion also equi es all egis e s o be emp y
a he end o he compu a ion, i.e., he e is an implici es o ze o a he end o a
(success ul) compu a ion, ha is why we say ha he de ice is pa ially blind. By
L(PBRM)we deno e he amily o se s o ec o s o na u al numbe s accep ed by
pa ially blind egis e machines. I is known (e.g., see [12]) ha pa ially blind
egis e machines a e s ic ly less powe ul han gene al egis e machines (hence,
han Tu ing machines); mo eo e , L(PBRM)cha ac e izes he Pa ikh se s o lan-
guages gene a ed by g aph-con olled o ma ix g amma s wi hou appea ance
checking.
Inpu -D i en Tissue P Au oma a 45
2.3 Coun e Au oma a
Regis e machines can also be equipped wi h an inpu ape o be able o p ocess
s ings, and he egis e s hen a e only used as auxilia y s o age. We hen call he
egis e s coun e s and he au oma on a coun e au oma on (we men ion ha in
he li e a u e sligh ly di e en de ini ions wi h espec o he ins uc ions may be
ound). The addi ional ins uc ion needed hen is a ead ins uc ion eading one
symbol om he inpu ape:
p: ( ead(a), K), wi h p∈B {h},K⊆B, and a∈T.
Tis he inpu alphabe , i.e., in sum we ob ain a coun e au oma on as a cons uc
M= (m, B, I, h, P, T).
A coun e au oma on accep s an inpu w∈T∗i and only i i s a s in some
ini ial s a e and wi h won i s inpu ape, and inally M eaches hha ing ead he
whole inpu s ing w. Wi hou loss o gene ali y, we again may assume all egis e s
o be emp y a he end o he compu a ion.
I is olklo e (e.g., see [23]) ha he amily o s ing languages accep ed by
coun e au oma a equals RE (in ac , only wo coun e s a e needed).
Pa ially blind coun e au oma a
As in he case o egis e machines, a coun e au oma on is called pa ially blind
i i canno check whe he a egis e is emp y, and accep ance by de ini ion e-
qui es he whole inpu o be ead and all coun e s o be emp y a he end o he
compu a ion. Fo basic esul s on pa ially blind coun e au oma a we e e o
he seminal pape [17]. The amily o s ing languages accep ed by pa ially blind
coun e au oma a is deno ed by L(PBCA).
2.4 Inpu -D i en Regis e Machines and Coun e Au oma a
An inpu -d i en egis e machine / coun e au oma on (an IDRM∗and IDCA∗,
espec i ely, o sho ) can be de ined in he ollowing way: any dec emen o an
inpu egis e / any eading o a e minal symbol ais ollowed by ixed sequences
o ins uc ions on he wo king egis e s / coun e s only depending on he inpu
egis e / he e minal symbol a. I each such sequence is o leng h exac ly one,
hen we speak o a eal- ime inpu -d i en egis e machine / coun e au oma on
(an IDRM and IDCA, espec i ely, o sho ).
In he case o an IDCA, hese sequences a e o he o m
p: ( ead(a), K)→q: (α( ), Kq), q ∈K,
wi h α∈ {ADD, SUB},1≤ ≤m, and hey could be w i en as one ex ended
ins uc ion
p: ( ead(a), α( ),Sq∈KKq).
46 A. Alhazo e al.
In a simila way, o an IDCA∗we eplace α( )by he whole sequence o in-
s uc ions ollowing he eading o he inpu symbol a. A simila no a ion can be
adap ed o he case o a SUB-ins uc ion on an inpu egis e ins ead o ead(a).
Mo eo e , analogous de ini ions and no a ions hold o he pa ially blind a ian s
o inpu -d i en egis e machines / coun e au oma a.
Rema k 1. We emphasize ha we ha e chosen a e y es ic ed a ian o wha i
means ha he ac ions on he wo king egis e s only depend on he inpu symbol
jus ead: no ma e which label he ead ins uc ion ead(a)has, i mus always be
ollowed by he same sequence α( ); only he b anching o labels om Sq∈KKq)
allows o aking di e en ac ions a e wa ds. u
Rema k 2. Allowing a se o ini ial labels as well as se s o labels in he ADD-
and SUB-ins uc ions may look qui e unusual, bu especially o he inpu -d i en
au oma a his ea u e u ns ou o be essen ial:
Assume we had allowed only one ini ial label iin any inpu -d i en coun e
au oma on. Now conside he ini e mul ise language {a, b}: assume he e is an
inpu -d i en pa ially blind coun e au oma on accep ing {a, b}. By de ini ion,
he ins uc ion assigned o he ini ial label imus be a ead ins uc ion. Wi h he
ini ial label i, only one o he ead ins uc ions ead(a)o ead(b)can be assigned,
hence, only ao only bcan be accep ed, a con adic ion.
A simila a gumen holds o pa ially blind egis e machines aking he inpu
se o wo-dimensional ec o s {(1,0),(0,1)}: he ins uc ion assigned o imus
be a SUB-ins uc ion ei he on egis e 1o on egis e 2, again leading o a
con adic ion.
On he o he hand, wi h ou mo e gene al de ini ion, we ge closu e unde
union o ee o L(X),X∈ {IDRM, IDCA, IDRM∗, IDCA∗}.u
3 Tissue P Au oma a as Mul ise Pushdown Au oma a
We now de ine a model o a issue P au oma on and i s inpu -d i en a ian s, i s
o he case o wo king wi h mul ise s as inpu objec s:
De ini ion 2. A issue P au oma on (a PA∗ o sho ) is a uple
Π= (L, V, Σ, Γ, R, g, I, F)
whe e
•Lis a se o labels iden i ying in a one- o-one manne he |L|cells o he issue
P sys em Π;
•Vis he alphabe o he sys em;
•Σ⊆Vis he (non-emp y) inpu alphabe o he sys em;
•Γ⊆Vis he (possibly emp y) memo y alphabe o he sys em, Γ∩Σ=∅;
Inpu -D i en Tissue P Au oma a 47
•Ris a se o ules o he o m (i, p)whe e i∈Land p∈Ins∗
V∪Del∗
V∪Sub∗
V,
i.e., pis an ex ended inse ion, dele ion o subs i u ion ule o e he alphabe
V; we may collec all ules om cell iin one se and hen w i e Ri={(i, p)|
(i, p)∈R}, so ha R=Si∈LRi; mo eo e , o he sake o conciseness, we
may simply w i e Ri={p|(i, p)∈R}, oo;
•gis a di ec ed g aph desc ibing he unde lying communica ion s uc u e o Π,
g= (N, E)wi h N=Lbeing he se o nodes o he g aph gand he se o
edges E⊆L×L;
•I⊆Lis he se o labels o ini ial cells one o hem con aining he inpu
mul ise wa he beginning o a compu a ion;
• ⊆Lis he se o labels o inal cells o accep ance.
I in he de ini ion abo e we ake p∈InsV∪DelV∪SubVins ead o p∈
Ins∗
V∪Del∗
V∪Sub∗
V, hen we speak o a PA ins ead o a PA∗.
A PA∗Πnow wo ks as ollows: The compu a ion o Πs a s wi h a esicle
con aining he inpu mul ise win one o he ini ial cells i∈I, and he compu a ion
p oceeds wi h de i a ion s eps un il a speci ic ou pu condi ion is ul illed.
In each de i a ion s ep, wi h he esicle enclosing he mul ise wbeing in cell k,
one ule om Rkis applied o wand he esul ing mul ise in i s esicle is mo ed
o a cell msuch ha (k, m)∈E.
As we a e dealing wi h memb ane sys ems, he classic ou pu condi ion is o
only conside hal ing compu a ions; ye in case o au oma a, he s anda d accep-
ance condi ion is eaching a inal s a e, which in ou case means eaching a inal
cell h, and, mo eo e , he esicle o be emp y. We will ake hese wo condi ions
as ou mode o accep ance in his pape , as wi h he esicle being emp y no dec e-
men ule can be applied any mo e and, mo eo e , i is gua an eed ha we ha e
“ ead he whole inpu ”. Only equi ing he esicle o be emp y o else equi ing
o ha e eached a inal cell wi h he esicle con aining no inpu symbol any mo e,
a e wo o he a ian s o accep ance.
The se o mul ise s accep ed by Πis deno ed by Psacc(Π). The amilies o
se s o ec o s o na u al numbe s accep ed by P A∗and P A wi h a mos n
cells a e deno ed by Ln( PA∗)and Ln( PA), espec i ely. I nis no bounded, we
simply omi he subsc ip in hese no a ions. In o de o speci y which ules a e
allowed in he PA∗and PA, we may explici ly speci y I∗, D∗, S∗and I, D, S,
espec i ely, o indica e he use o (ex ended) inse ion, dele ion, and subs i u ion
ules. Fo example, L( PA, ID) hen indica es ha only inse ion and dele ion
ules a e used.
Rema k 3. The model o a PA∗comes e y close o he model o a mul ise push-
down au oma on as in oduced in [18]; in ac , he amily o se s o ec o s o
na u al numbe s accep ed by hese mul ise pushdown au oma a equals L( PA∗).
A o mal p oo would go a beyond he scope o his pape , bu he basic simi-
la i y o hese wo models becomes ob ious when iden i ying he cells in he PA∗
wi h he s a es in he mul ise pushdown au oma on; mo ing he esicle om one
54 A. Alhazo e al.
ΠD= (L={1,2,3,4,5}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={5}),
V={a1,[,]},
Σ={[,]},
Γ={a1},
R={(1, ead ( [ )),(2, I (a1)),(3, ead ( ] )),(4, D (a1))},
E={(1,2),(2,1),(2,3),(3,4),(4,1),(4,3),(4,5)}.
The wo cons uc ions elabo a ed abo e implemen he ollowing de ini ion o
a well- o med b acke exp ession wo e he alphabe o b acke s {[,]}:
• o e e y p e ix o w, he numbe o closing b acke s ]mus no exceed he
numbe o opening b acke s [;
• he numbe o closing b acke s ]in wequals he numbe o opening b acke s [.
Hence, du ing he whole compu a ion, he (non-nega i e) di e ence be ween
he numbe o opening and he numbe o closing b acke s is s o ed as he numbe
o symbols a1; a he end, his numbe mus be ze o, which is gua an eed by he
accep ance condi ions. u
L(IDPBCA )e en con ains a non-con ex - ee language:
Example 2. The language Lil ={anbmcndm|m, n ≥1}is no con ex - ee, bu
accep ed by he ollowing IDPAL Πil:
Πil = (L={1,...,9}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={9}),
V={a1, a2, a, b, c, d},
Σ={a, b, c, d},
Γ={a1, a2},
R={(1, ead (a)),(2, I (a1)),(3, ead (b)),(4, I (a2)),
(5, ead (c)),(6, D (a1)),(7, ead (d)),(8, D (a2))},
E={(1,2),(2,1),(2,3),(3,4),(4,3),
(4,5),(5,6),(6,5),(6,7),(7,8),(8,7),(8,9)}.
By his cons uc ion, we conclude Lil ∈ L( IDPAL , ID).u
Fo he language conside ed in he nex example we show ha i is in
L( IDPAL∗ ), bu we claim ha i is no in L( IDP AL ):
Example 3. Le k > 2and conside he s ing language Lk={b1n. . . bkn|n≥1},
which is no con ex - ee, bu accep ed by he ollowing IDPAL∗ Π:

Inpu -D i en Tissue P Au oma a 55
1
s a
ead(a)
2
I(a1)
3
ead(b)
4
I(a2)
5
ead(c)
6
D(a1)
7
ead(d)
8
D(a2)
9
Fig. 1. G aphic ep esen a ion o he IDP AL Πil.
Πk= (L={1,...,2k+ 1}, V, Σ, Γ, R, g = (L, E), I ={1}, F ={2k+ 1}),
V={ai, bi|1≤i≤k},
Σ={bi|1≤i≤k},
Γ={ai|1≤i≤k},
R={(1, ead (b1)),(2, I (a2. . . ak))}
∪ {(2j−1, ead (bj)),(2j, D (aj)) |1< j ≤k},
E={(2j−1,2j),(2j, 2j−1),(2j, 2j+ 1) |1≤j≤k}.
Wi hou p oo we claim ha Lk/∈ L( IDPAL ).u
5 Conclusion and Fu u e Resea ch
In his pape , we ha e in oduced issue P au oma a as a speci ic model o mul ise
au oma a as well as inpu -d i en issue P au oma a whe e he ules o be applied
depend on he inpu symbol. Taking s ings as inpu objec s, hese a e ei he ead
om an inpu ape o de ined by he sequence o symbols aken in, and as an
addi ional s o age o a mul ise o di e en symbols we use a esicle which mo es
om one cell o he issue P sys em o ano he one depending on he inpu symbol;
he inpu symbol a he same ime de e mines whe he (one o mo e) symbols a e
added o he mul ise in he esicle o emo ed om he e and whe e he esicle
mo es a e wa ds. The gi en inpu is accep ed i he whole inpu has been ead
and he esicle has eached a inal cell and/o is emp y a his momen . When
using mul ise s as inpu objec s, hese a e enclosed in he esicle in he inpu cell
a he beginning o a compu a ion, which esicle hen will also ake he addi ional
symbols. The gi en inpu mul ise is accep ed i no inpu symbols a e p esen any
mo e and he esicle has eached a inal cell and is emp y a his momen .
As ules ope a ing on he mul ise enclosed in he esicle when ead-
ing/consuming an inpu symbol we ha e used inse ion, dele ion, and subs i u ion
o mul ise s, wo king in he sequen ial de i a ion mode. As es ic ed a ian s, we
ha e conside ed sys ems wi hou allowing subs i u ion o mul ise s and sys ems
only allowing symbols o be inse ed o dele ed (o subs i u ed).
56 A. Alhazo e al.
We ha e shown how inpu -d i en issue P au oma a wi h mul ise s and s ings
can be cha ac e ized by inpu -d i en egis e machines and inpu -d i en coun e
au oma a, espec i ely. Mo eo e , we ha e exhibi ed some illus a i e examples,
o example, how he Dyck language o e en some non-con ex ee languages can
be accep ed by simple a ian s o inpu -d i en issue P au oma a.
Se e al challenging opics emain o u u e esea ch: o example, a cha ac e -
iza ion o he language classes accep ed by se e al a ian s o issue P au oma a
accep ing mul ise s o s ings, especially o he inpu -d i en a ian s, in oduced
in his pape is s ill open.
As accep ance condi ion we ha e only conside ed eaching he inal cell hwi h
an emp y esicle. The o he a ian s o accep ance, i.e., only equi ing he esicle o
be emp y o else equi ing o ha e eached he inal cell wi h he esicle con aining
no inpu symbol any mo e, a e o be in es iga ed in he u u e in mo e de ail.
Re e ences
1. Alhazo , A., F eund, R., Heikenwälde , H., Oswald, M., Rogozhin, Yu., Ve lan, S.: Se-
quen ial P sys ems wi h egula con ol. In: Csuhaj-Va jú, E., Gheo ghe, M., Rozen-
be g, G., Salomaa, A., Vaszil, Gy. (eds.) Memb ane Compu ing - 13 h In e na ional
Con e ence, CMC 2012, Budapes , Hunga y, Augus 28-31, 2012, Re ised Selec ed
Pape s. Lec u e No es in Compu e Science, ol. 7762, pp. 112–127. Sp inge (2013).
h ps://doi.o g/10.1007/978-3-642-36751-9_9
2. Alhazo , A., F eund, R., I ano , S., Ve lan, S.: ( issue) P sys ems wi h esi-
cles o mul ise s. In: Csuhaj-Va jú, E., Dömösi, P., Vaszil, Gy. (eds.) P oceedings
15 h In e na ional Con e ence on Au oma a and Fo mal Languages, AFL 2017,
Deb ecen, Hunga y, Sep embe 4-6, 2017. EPTCS, ol. 252, pp. 11–25 (2017).
h ps://doi.o g/10.4204/EPTCS.252.6
3. Alu , R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.)
P oceedings o he 36 h Annual ACM Symposium on Theo y o Com-
pu ing, Chicago, IL, USA, June 13-16, 2004. pp. 202–211. ACM (2004).
h ps://doi.o g/10.1145/1007352.1007390
4. Alu , R., Madhusudan, P.: Adding nes ing s uc u e o wo ds. J. ACM 56(3), 16:1–
16:43 (2009). h ps://doi.o g/10.1145/1516512.1516518
5. Bensch, S., Holze , M., Ku ib, M., Malche , A.: Inpu -d i en s ack au oma a. In:
Bae en, J.C.M., Ball, T., de Boe , F.S. (eds.) Theo e ical Compu e Science - 7 h
IFIP TC 1/WG 2.2 In e na ional Con e ence, TCS 2012, Ams e dam, The Ne he -
lands, Sep embe 26-28, 2012. P oceedings. Lec u e No es in Compu e Science,
ol. 7604, pp. 28–42. Sp inge (2012). h ps://doi.o g/10.1007/978-3-642-33475-7_3
6. on B aunmühl, B., Ve beek, R.: Inpu -d i en languages a e ecognized in log n space.
In: Ka pinski, M. (ed.) Founda ions o Compu a ion Theo y. pp. 40–51. Sp inge ,
Be lin, Heidelbe g (1983)
7. Csuhaj-Va jú, E., Ma ín-Vide, C., Mi ana, V.: Mul ise au oma a. In: Calude,
C.S., Păun, Gh., Rozenbe g, G., Salomaa, A. (eds.) Mul ise P ocessing. pp. 69–83.
Sp inge , Be lin, Heidelbe g (2001)
Inpu -D i en Tissue P Au oma a 57
8. Csuhaj-Va jú, E., Vaszil, Gy.: P au oma a o pu ely communica ing accep ing p
sys ems. In: Păun, Gh., Rozenbe g, G., Salomaa, A., Zand on, C. (eds.) Memb ane
Compu ing. pp. 219–233. Sp inge , Be lin, Heidelbe g (2003)
9. Dassow, J., Păun, Gh.: On he powe o memb ane compu ing. J. UCS 5(2), 33–49
(1999). h ps://doi.o g/10.3217/jucs-005-02-0033
10. Dymond, P.W.: Inpu -d i en languages a e in log n dep h. In o ma ion P ocessing
Le e s 26(5), 247–250 (1988). h ps://doi.o g/10.1016/0020-0190(88)90148-2
11. F eund, R.: P au oma a: New ideas and esul s. In: Bo dihn, H., F eund, R., Nagy,
B., Vaszil, Gy. (eds.) Eigh h Wo kshop on Non-Classical Models o Au oma a and
Applica ions, NCMA 2016, Deb ecen, Hunga y, Augus 29-30, 2016. P oceedings.
[email protected] , ol. 321, pp. 13–40. Ös e eichische Compu e Gesellscha (2016)
12. F eund, R., Iba a, O., Păun, Gh., Yen, H.C.: Ma ix languages, egis e machines,
ec o addi ion sys ems. Thi d B ains o ming Week on Memb ane Compu ing pp.
155–167 (2005)
13. F eund, R., Kogle , M., Rogozhin, Yu., Ve lan, S.: G aph-con olled inse ion-dele ion
sys ems. In: P oceedings Twel h Annual Wo kshop on Desc ip ional Complexi y o
Fo mal Sys ems, DCFS 2010, Saska oon, Canada, 8-10 h Augus 2010. pp. 88–98
(2010). h ps://doi.o g/10.4204/EPTCS.31.11
14. F eund, R., Oswald, M.: Tissue P sys ems and (mem)b ane sys ems wi h ma e and
d ip ope a ions wo king on s ings. Elec . No es Theo . Compu . Sci. 171(2), 105–
115 (2007). h ps://doi.o g/10.1016/j.en cs.2007.05.011
15. F eund, R., Păun, Gh.: How o ob ain compu a ional comple eness in P sys-
ems wi h one ca alys . In: P oceedings Machines, Compu a ions and Uni e sal-
i y 2013, MCU 2013, Zü ich, Swi ze land, Sep embe 9-11, 2013. pp. 47–61 (2013).
h ps://doi.o g/10.4204/EPTCS.128.13
16. F eund, R., Rogozhin, Yu., Ve lan, S.: Gene a ing and accep ing P sys ems wi h
minimal le and igh inse ion and dele ion. Na u al Compu ing 13(2), 257–268
(2014). h ps://doi.o g/10.1007/s11047-013-9396-3
17. G eibach, S.A.: Rema ks on blind and pa ially blind one-way mul icoun e machines.
Theo e ical Compu e Science 7, 311–324 (1978). h ps://doi.o g/10.1016/0304-
3975(78)90020-8
18. Kudlek, M., To zke, P., Ze zsche, G.: Mul ise pushdown au oma a. Fundam. In o m.
93(1-3), 221–233 (2009). h ps://doi.o g/10.3233/FI-2009-0098
19. Ku ib, M., Malche , A., Wendland , M.: Tinpu -d i en pushdown, coun e ,
and s ack au oma a. Fundamen a In o ma icae 155(1-2), 59–88 (2017).
h ps://doi.o g/10.3233/FI-2017-1576
20. Ku ib, M., Malche , A., Wendland , M.: Queue au oma a: Founda ions andÂăde el-
opmen s. In: Adama zky, A. (ed.) Re e sibili y and Uni e sali y: Essays P esen ed o
Kenichi Mo i a on he Occasion o his 70 h Bi hday. pp. 385–431. Sp inge (2018).
h ps://doi.o g/10.1007/978-3-319-73216-9_19
21. Ma ín-Vide, C., Pazos, J., Păun, Gh., Rod íguez-Pa ón, A.: A new class o symbolic
abs ac neu al ne s: Tissue P sys ems. In: Compu ing and Combina o ics, pp. 290–
299. Sp inge (2002). h ps://doi.o g/10.1007/3-540-45655-4_32
22. Mehlho n, K.: Pebbling moun ain anges and i s applica ion o dc l- ecogni ion. In:
de Bakke , J., an Leeuwen, J. (eds.) Au oma a, Languages and P og amming. pp.
422–435. Sp inge , Be lin, Heidelbe g (1980)
23. Minsky, M.L.: Compu a ion. Fini e and In ini e Machines. P en ice Hall, Englewood
Cli s, NJ (1967)
58 A. Alhazo e al.
24. Okho in, A., Salomaa, K.: Inpu -d i en pushdown au oma a: nonde e minism and
unambigui y. In: Bensch, S., D ewes, F., F eund, R., O o, F. (eds.) Fi h Wo kshop
on Non-Classical Models o Au oma a and Applica ions - NCMA 2013, Umeå, Swe-
den, Augus 13 - Augus 14, 2013, P oceedings. [email protected] , ol. 294, pp. 31–33.
Ös e eichische Compu e Gesellscha (2013)
25. Okho in, A., Salomaa, K.: Inpu -d i en pushdown au oma a wi h limi ed nonde-
e minism - (in i ed pape ). In: Shu , A.M., Volko , M.V. (eds.) De elopmen s in
Language Theo y - 18 h In e na ional Con e ence, DLT 2014, Eka e inbu g, Russia,
Augus 26-29, 2014. P oceedings. Lec u e No es in Compu e Science, ol. 8633, pp.
84–102. Sp inge (2014). h ps://doi.o g/10.1007/978-3-319-09698-8_9
26. Okho in, A., Salomaa, K.: Desc ip ional complexi y o unambiguous inpu -
d i en pushdown au oma a. Theo e ical Compu e Science 566, 1–11 (2015).
h ps://doi.o g/10.1016/j. cs.2014.11.015
27. Okho in, A., Salomaa, K.: S a e complexi y o ope a ions on inpu -
d i en pushdown au oma a. J. Compu . Sys . Sci. 86, 207–228 (2017).
h ps://doi.o g/10.1016/j.jcss.2017.02.001
28. Oswald, M.: P Au oma a. Ph.D. hesis, Facul y o Compu e Science, TU Wien
(2003)
29. Paun, A., Păun, Gh.: The powe o communica ion: P sys ems wi h
sympo /an ipo . New Gene a ion Compu . 20(3), 295–306 (2002).
h ps://doi.o g/10.1007/BF03037362
30. Păun, Gh.: Compu ing wi h Memb anes. Jou nal o Compu e and Sys em Sciences
61(1), 108–143 (2000). h ps://doi.o g/10.1006/jcss.1999.1693
31. Păun, Gh., Rozenbe g, G., Salomaa, A. (eds.): The Ox o d Handbook o Memb ane
Compu ing. Ox o d Uni e si y P ess, Ox o d, England (2010)
32. Rozenbe g, G., Salomaa, A. (eds.): Handbook o Fo mal Languages, ol. 1-3. Sp inge
(1997)
33. Bulle in o he In e na ional Memb ane Compu ing Socie y (IMCS).
h p://memb anecompu ing.ne /IMCSBulle in/index.php
34. The P Sys ems Websi e. h p://ppage.psys ems.eu/