P Sys ems wi h Minimal Le and Righ
Inse ion and Dele ion
Rudol F eund1, Yu ii Rogozhin2, and Se gey Ve lan3
1Facul y o In o ma ics, Vienna Uni e si y o Technology
Fa o i ens . 9, 1040 Vienna, Aus ia
Email: [email p o ec ed]
2Ins i u e o Ma hema ics and Compu e Science
Academy o Sciences o Moldo a
S . Academiei 5, Chi¸sin˘au, MD-2028, Moldo a
Email: [email p o ec ed]
3LACL, D´epa emen In o ma ique, Uni e si ´e Pa is Es
61, a . G´en´e al de Gaulle, 94010 C ´e eil, F ance
Email: [email p o ec ed]
Summa y. In his a icle we in es iga e he ope a ions o inse ion and dele ion pe -
o med a he ends o a s ing. We show ha using hese ope a ions in a P sys ems
amewo k (which co esponds o using specific a ian s o g aph con ol), compu a ional
comple eness can e en be achie ed wi h he ope a ions o le and igh inse ion and
dele ion o only one symbol.
1 In oduc ion
The ope a ions o le and igh inse ion and dele ion ha we conside in his
a icle co espond o he ope a ions o le and igh conca ena ion and quo ien
wi h a fini e language. While hese ope a ions a e known o a long ime, hei
join in es iga ion in a dis ibu ed amewo k o igina es om he a ea o na u-
al compu ing, whe e hey we e used in he con ex o ne wo ks o e olu iona y
p ocesso s (NEP) [7]. Such ne wo ks a e a special ype o ne wo ks o language
p ocesso s [6] ha ea u e a se o ( ew i ing) nodes ew i ing languages and a -
e ha edis ibu ing some egula subse s be ween he nodes. In ne wo ks o
e olu iona y p ocesso s, he ew i ing ope a ions a e eplaced by h ee ypes o
ope a ions ha ing a biological mo i a ion: inse ion, dele ion, and mu a ion (sub-
s i u ion). The co esponding sys ems a e qui e powe ul and we e e o [8] o
mo e de ails. The edis ibu ion o he node con en s based on a egula condi ion
is a e y powe ul ope a ion. Accep ing hyb id ne wo ks o e olu iona y p ocesso s
(AHNEP) eplace his condi ion by andom con ex condi ions, howe e , he se
124 R. F eund, Y. Rogozhin, S. Ve lan
o ope a ions is changed and now includes he inse ion and dele ion ope a ions a
he ex emi ies o he s ings; we e e o [21, 9] o mo e de ails on AHNEP.
The ope a ions o inse ion and dele ion on he ex emi ies o a s ing can also
be seen as a pa icula case o a mo e gene al a ian , whe e inse ion and dele ion
can be pe o med anywhe e in he s ing. The inse ion ope a ion defined in such
a way was fi s conside ed in [14, 15] and a e ha ela ed inse ion and dele ion
ope a ions we e in es iga ed in [17, 18]. Ano he gene aliza ion o he inse ion
and dele ion ope a ions ha in ol es he checking o con ex s o he inse ion and
dele ion was conside ed wi h a linguis ic mo i a ion in [13, 20] and wi h a biological
mo i a ion in [4, 5, 18, 26]. Gene ally, i he leng h o he con ex s and/o o he
inse ed and dele ed s ings a e big enough, hen he inse ion-dele ion closu e o
a fini e language leads o compu a ional comple eness. The e a e nume ous esul s
es ablishing he desc ip ional complexi y pa ame e s sufficien o achie e his goal,
we e e o [31, 30] o an o e iew o his a ea.
Some desc ip ional complexi y pa ame e s lead o a ian s ha a e no com-
pu a ionally comple e. An in es iga ion o inse ion and dele ion ope a ions com-
bined wi h egula ing mechanisms was done o hese cases, mo e p ecisely, wi h
he g aph-con olled, he ma ix, and he andom-con ex con ols [11, 28, 16]. As
i was shown in hese a icles, in mos o he cases he addi ional con ol leads
o compu a ional comple eness. The g aph-con olled egula ion is o pa icula
in e es , as i can be ela ed o he no ion o P sys ems. Such sys ems o mal-
ize he unc ioning o a li ing cell ha opologically delimi s p ocessing uni s by
memb anes, hus leading o a ee (o g aph) s uc u e o p ocessing nodes. The
elemen s p ocessed in some node (memb ane) hen a e dis ibu ed among he
neighbo s in he s uc u e. We e e o [24, 25] and o he web page [29] o mo e
de ails on P sys ems. In he case o he ope a ions o inse ion and dele ion ac ing
on s ings his di ec ly co esponds o a g aph con ol whe e he con ol nodes
co espond o he memb anes.
The esea ch on con ex - ee inse ion and dele ion (i.e., wi hou con ex ual
dependency) shows ha i he leng hs o he inse ed and dele ed s ings a e 2 and
3 (o 3 and 2), espec i ely, hen he inse ion-dele ion closu e o fini e languages
is compu a ionally comple e [22]. When one o hese pa ame e s is dec eased, his
esul is no ue anymo e [32]; mo eo e , e en he g aph-con olled a ian canno
achie e compu a ional comple eness [19]. This changes when a g aph con ol wi h
appea ance checking is used [1] o in he case o a andom con ex con ol [16]. In
bo h a ian s, minimal ope a ions (in ol ing only one symbol) we e conside ed,
leading o RE ( he amily o ecu si ey enume able languages) in he case o se -
con olled andom con ex condi ions and o PsRE ( he amily o Pa ikh se s o
RE) in he case o g aph con ol wi h appea ance checking.
We no e ha he ope a ions o le and igh inse ion and dele ion a e incom-
pa able wi h no mal inse ion and dele ion: because o he posi ional in o ma ion,
he egula language a+b+can be ob ained e en wi h le and igh inse ions o
only one symbol, ye no when inse ions a e possible a a bi a y posi ions in he
s ing. On he o he hand, he Dyck language canno be ob ained when inse ion
P Sys ems wi h Minimal Le and Righ Inse ion and Dele ion 125
is only possible a he ends o he s ings, while wi h no mal inse ion his can be
done easily. In [1, 3], le and igh inse ion and dele ion ope a ions (unde he
name o exo-inse ion and -dele ion) we e conside ed in he P sys ems amewo k
(i.e., wi h a g aph con ol) and i was shown ha sys ems wi h inse ion o s ings
o leng h 2 ( espec i ely 1) and dele ion o s ings o leng h 1 ( espec i ely 2)
lead o compu a ional comple eness. In he case o minimal inse ion and dele ion
(i.e., o only one symbol), a p io i y o dele ion o e inse ion (co esponding o
an appea ance check) was used o show compu a ional comple eness.
In his a icle we con inue hese in es iga ions and we conside P sys ems wi h
minimal le and igh inse ion and dele ion and p o e ha compu a ional com-
ple eness can be achie ed e en in his case, wi h he s uc u e o he P sys em we
need being ma ix-like. We also di ec ly show ha ma ix g amma s using minimal
le inse ion and minimal igh dele ion ules a e compu a ionally comple e (wi h
ma ices o leng h a mos 3). Mo eo e , we also p o e ha using an addi ional
minimal mu a ion ope a ion (subs i u ion o one symbol by ano he one) allows
o educing he heigh o he ee s uc u e o he P sys em o he minimum size
1.
2 P elimina ies
A e some p elimina ies om o mal language heo y, we define he s ing ew i -
ing ules o be used in his pape . As s ing ew i ing sys ems, we will conside
Pos sys ems, ma ix g amma s, and sequen ial P sys ems. Mo eo e , we will gi e
some examples and p elimina y esul s o illus a e ou defini ions.
The se o non-nega i e in ege s is deno ed by N. An alphabe Vis a fini e non-
emp y se o abs ac symbols. Gi en V, he ee monoid gene a ed by Vunde
he ope a ion o conca ena ion is deno ed by V∗; he elemen s o V∗a e called
s ings, and he emp y s ing is deno ed by λ;V∗ {λ}is deno ed by V+. Le
{a1, ..., an}be an a bi a y alphabe ; he numbe o occu ences o a symbol ai
in xis deno ed by |x|ai; he numbe o occu ences o all symbols om Vin xis
deno ed by |x|. The amily o ecu si ely enume able s ing languages is deno ed
by RE. 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 as [10, 27].
We he e conside s ing ew i ing ules only wo king a he ends o a s ing:
Pos ew i ing ule P[x/y] wi h x, y ∈V∗:P[x/y] (wx) = yw o w∈V∗.
Le subs i u ion SL[x/y] wi h x, y ∈V∗:SL[x/y] (xw) = yw o w∈V∗.
Righ subs i u ion SR[x/y] wi h x, y ∈V∗:SR[x/y] (wx) = wy o w∈V∗.
I in a (le o igh ) subs i u ion SL[x/y] o SR[x/y]xis emp y, hen we
call i an inse ion and w i e IL[y] and IR[y], espec i ely; i in a (le o igh )
subs i u ion SL[x/y] o SR[x/y]yis emp y, hen we call i a dele ion and w i e
DL[x] and DR[x], espec i ely. I we only inse one symbol a, hen we will also
w i e +a,a+, −a, and a− o IL[a], IR[a], DL[a], and DR[a], espec i ely.
126 R. F eund, Y. Rogozhin, S. Ve lan
In gene al, a (s ing ew i ing) g amma Go ype Xis a cons uc (V, T, A, P )
whe e Vis a se o symbols,T⊆Vis a se o e minal symbols,A∈V+is he
axiom, and Pis a fini e se o ules o ype X. Each ule p∈Pinduces a ela ion
=⇒p⊆V∗×V∗;pis called applicable o a s ing x∈V∗i and only i he e exis s
a leas one s ing y∈V∗such ha (x, y)∈=⇒p; we also w i e x=⇒py.
The de i a ion ela ion =⇒Gis he union o all =⇒p, i.e., =⇒G=∪p∈P=⇒p. The
eflexi e and ansi i e closu e o =⇒Gis deno ed by ∗
=⇒G.
The language gene a ed by Gis he se o all e minal s ings de i able om
he axiom, i.e., L(G) = { ∈T∗|A∗
=⇒G }. The amily o languages gene a ed
by g amma s o ype Xis deno ed by L(X).
In gene al, we w i e Sk,m
R o a ype o g amma s using only subs i u ion ules
SR[x/y] wi h |x| ≤ kand |y| ≤ m. In he same way, we define he ype Sk,m
L o a
ype o g amma s using only subs i u ion ules SL[x/y] wi h |x| ≤ kand |y| ≤ m,
as well as he ypes Im
L,Im
R,Dk
L, and Dk
R, espec i ely. The ype DkImallows
o he dele ion o s ings wi h leng h ≤kand o he inse ion o s ings wi h
leng h ≤m. I , in addi ion, we also allow subs i u ions SR[x/y] wi h |x| ≤ k′and
|y| ≤ m′, we ge he ype DkImSk′m′; we obse e ha he ype DkImSk′m′is
subsumed by he ype Sk′m′i k≤k′and m≤m′. I we allow he pa ame e s k
and/o m o be a bi a ily la ge, we jus omi hem, e.g., DI is he ype allowing
o use dele ions and inse ions o s ings o a bi a y leng hs.
Example 1. Le G= (V, T, A, P ) be a egula g amma , i.e., he ules in Pa e o
he o m A→bC and A→λwi h A, C ∈V Tand b∈T. Then he g amma
G′= (V, T, A, {SR[A/y]|A→y∈P}) wi h subs i u ion ules gene a es he same
language as G, i.e., L(G′) = L(G). Hence, wi h REG deno ing he amily o
egula languages, we ob iously ha e go REG ⊆ L (S1,2
R).
I is no difficul o check ha g amma s o ype D1I1S1ha e a a he lim-
i ed compu a ional powe . Indeed, we can show he ollowing ep esen a ion o
languages gene a ed by g amma s o ype D1I1S1:
Theo em 1. E e y language L⊆T∗in L(D1I1S1)can be w i en in he o m
T∗
lST∗
whe e Tl, T ⊆Tand Sis a ini e subse o T∗.
P oo . Le G= (V, T, A, P ) be a g amma o ype D1I1S1and le N:= V T.
We fi s cons uc he s a se Sas ollows: Conside all possible de i a ions in
G om Awi h only using subs i u ions and dele ions, bu wi hou loops, i.e., no
s ing is allowed o appea mo e han once in such a de i a ion, which means ha
all hese de i a ions a e o bounded leng h (bounded by he numbe o s ings
in Vo leng h a mos |V|).Then Sconsis s o all e minal s ings ob ained in
his way (finding hese s ings is a fini ely bounded p ocess, as o each o he
possible s ings in Vo leng h a mos |V|, a mos |P| ules can be applied). A
symbol om N emaining inside a s ing blocks ha s ing om e e becoming
e minal by applying ules om P, and dele ion o a symbol can be a oided by
P Sys ems wi h Minimal Le and Righ Inse ion and Dele ion 127
jus no in oducing he symbol which by a sequence o minimal subs i u ions
would lead o he symbol o be dele ed. Hence, o cons uc ing he se s Tl(T ,
espec i ely) we can es ic ou sel es o he e minal symbols bei he di ec ly
inse ed by minimal inse ion ules Il[b] (I [b], espec i ely) o ob ained by a
sequence o one minimal inse ion oge he wi h a bounded (by |V|) numbe o
minimal subs i u ions Sl[a/b] (S [a/b], espec i ely).
The e o e, in sum L(G) can be w i en as he fini e union o languages gene -
a ed by g amma s o ype I1, i.e., L(G) = ∪w∈SL(Gw) whe e
Gw= (T, T, w, {Il[b]|b∈Tl}∪{I [b]|b∈T }).
In ac , his ep esen a ion o languages in L(D1I1S1)means ha o he ype
D1I1S1we could o ge minimal dele ions and subs i u ions and ins ead conside
fini e subse s o axioms ins ead o a single axiom. Pu ing an Ain on o he
ypes o his a ian o g amma s, we jus ha e p o ed ha
L(A-D1I1S1)=L(A-I1).
2.1 Pos Sys ems
APos sys em is a g amma using only Pos ew i ing ules (a g amma o ype
PS). A Pos sys em (V, T, A, P) is said o be in no mal o m (a g amma o ype
PSNF ) i and only i he Pos ew i ing ules P[x/y] in Pa e only o he o ms
P[ab/c], P[a/bc], P[a/b], and P[a/λ], wi h a, b, c ∈V. A Pos sys em (V, T, A, P)
is said o be in Z-no mal o m (a g amma o ype P SZNF) i and only i i is in
no mal o m and, mo eo e , he e exis s a special symbol Z∈V Tsuch ha
•Zappea s only once in he s ing xo a Pos ew i ing ule P[x/y], and his
ule is P[Z/λ];
•i he ule P[Z/λ] is applied, he de i a ion in he Pos sys em s ops yielding
a e minal s ing;
•a e minal s ing can only be ob ained by applying he ule P[Z/λ].
Al hough basic esul s conce ning Pos sys ems a e olklo e since many yea s,
e.g., see [23], we need he special Z-no mal o m o he p oo o ou main heo em;
he ollowing esul is an immedia e consequence o he p oo gi en in [12] o
Lemma 1 he e:
Theo em 2. Fo e e y ecu si ely enume able language L⊆T∗ he e exis s a Pos
ew i ing sys em G,G= (V, T, A, P), in Z-no mal o m such ha L(G) = L, i.e.,
L(PS) = L(PSNF) = L(PSZNF) = RE.
2.2 Ma ix G amma s
Ama ix g amma o ype Xis a cons uc GM= (G, M) whe e G= (V, T, A, P)
is a g amma o ype X,Mis a fini e se o sequences o he o m (p1, . . . , pn),
n≥1, o ules in P. Fo w, z ∈V∗we w i e w=⇒GMzi he e a e a ma ix

128 R. F eund, Y. Rogozhin, S. Ve lan
(p1, . . . , pn) in Mand objec s wi∈V∗,1≤i≤n+ 1, such ha w=w1,
z=wn+1,and, o all 1 ≤i≤n,wi=⇒Gwi+1. The maximal leng h no a ma ix
(p1, . . . , pn)∈Mis called he deg ee o GM.
L(GM) = { ∈T∗|A=⇒∗
GM }is he language gene a ed by GM. The amily
o languages gene a ed by ma ix g amma s o ype X(o deg ee a mos n) is
deno ed by L(X-MAT) (L(X-MATn)).
Theo em 3. L(D2I2-MAT2)=L(D1I1-MAT3)=L(PSNF) = RE.
P oo . F om Theo em 2 we know ha L(PSNF) = RE, hence, we will only show
ha o e e y Pos sys em G= (V, T, A, P) in no mal o m we a e able o cons uc
equi alen ma ix g amma s G1= (G, M1) and G2= (G, M2) o ype D2I2and
o ype D1I1, espec i ely:
M1={(DR[x], IL[y]) |P[x/y]∈P},
M2={(DR[b], DR[a], IL[c]) |P[ab/c]∈P}
∪ {(DR[a], IL[c], IL[b]) |P[a/bc]∈P}
∪ {(DR[a], IL[b]) |P[a/b]∈P}
∪ {(DR[a]) |P[a/λ]∈P}.
As each ule in Gis di ec ly simula ed by a ma ix in M1and in M2, espec-
i ely, we immedia ely in e L(G) = L(G1) = L(G2). 
Whe eas he ma ices in M1a e only o leng h 2, he deg ee o M2is 3; i
emains as an open ques ion whe he also wi h ules o ype D1I1we could dec ease
he deg ee o 2 o no ; we conjec u e ha he answe is no. As we ha e shown
in Theo em 1, wi h g amma s using ules o ype D1I1S1we a e no able o
ob ain RE, we e en emain below he egula language class; hence, we need such
egula ing mechanisms as ma ices o each compu a ional compleness.
2.3 P Sys ems
We now in oduce ano he a ian o guide he de i a ions in a g amma using ules
o hose ypes in oduced abo e, i.e., specific a ian s o le and igh subs i u ion
ules.
A(sequen ial) P sys em o ype Xwi h ee heigh nis a cons uc Π=
(G, µ, R, i0) whe e G= (V, T, A, P ) is a g amma wi h ules o ype Xand
•µis he memb ane ( ee) s uc u e o he sys em wi h he heigh o he ee
being n(µusually is ep esen ed by a s ing con aining co ec ly nes ed ma ked
pa en heses); we assume he memb anes, i.e., he nodes o he ee ep esen ing
µ, being uniquely labelled by labels om a se Lab;
•Ris a se o ules o he o m (h, , a ) whe e h∈Lab, ∈P, and a , called
he a ge indica o , is aken om he se {he e, in, ou }∪{inj|1≤j≤n};
he ules assigned o memb ane h o m he se Rh={( , a )|(h, , a )∈R},
i.e., Rcan also be ep esen ed by he ec o (Rh)h∈Lab;
P Sys ems wi h Minimal Le and Righ Inse ion and Dele ion 129
•i0is he ini ial memb ane whe e he axiom Ais pu a he beginning o a
compu a ion.
As we only ha e o ollow he ace o a single s ing du ing a compu a ion o
he P sys em, a configu a ion o Πcan be desc ibed by a pai (w, h) whe e wis he
cu en s ing and his he label o he memb ane cu en ly con aining he s ing w.
Fo wo configu a ions (w1, h1) and (w2, h2) o Πwe w i e (w1, h1) =⇒Π(w2, h2)
i we can pass om (w1, h1) o (w2, h2) by applying a ule (h1, , a )∈R, i.e.,
w1=⇒ w2and w2is sen om memb ane h1 o memb ane h2acco ding o he
a ge indica o a . Mo e specifically, i a =he e, hen h2=h1; i a =ou ,
hen he s ing w2is sen o he egion h2immedia ely ou side memb ane h1; i
a =inh2, hen he s ing is mo ed om egion h1 o he egion h2immedia ely
inside egion h1; i a =in, hen he s ing w2is sen o one o he egions
immedia ely inside egion h1.
A sequence o ansi ions be ween configu a ions o Π, s a ing om he ini ial
configu a ion (A, i0), is called a compu a ion o Π. A hal ing compu a ion is a
compu a ion ending wi h a configu a ion (w, h) such ha no ule om Rhcan
be applied o wanymo e; (w, h) is called he esul o his hal ing compu a ion i
w∈T∗.L(Π), he language gene a ed by Π, consis s o all s ings o e Twhich
a e esul s o a hal ing compu a ion in Π.
By L(X-LP) (L(X-LP⟨n⟩)) we deno e he amily o languages gene a ed by
P sys ems (o ee heigh a mos n) using ules o ype X. I only he a ge s
he e, in, ou a e used, hen he P sys em is called simple, and he co esponding
amilies o languages a e deno ed by L(X-LsP) (L(X-LsP ⟨n⟩)).
Example 2. Le Π= (G, [1[2]2[3]3[4]4]1, R, 1) be a P sys em o ype D1
RI2
L
wi h
G= ({a, B},{a},{DR[a], DR[B], IL[aa], IL[B]}, aB),
R={(1, DR[a], in2),(1, DR[B], in3),(1, DR[B], in4)}
∪ {(2, IL[aa], ou ),(3, IL[B], ou )}
The compu a ions in Πs a wi h aB in memb ane ( egion) 1. In gene al,
s a ing wi h a s ing a2nB,n≥0, in memb ane 1, we may ei he dele e B
by he ule (1, DR[B], in4), ge ing a2nas he e minal esul in he elemen a y
memb ane 4 (a memb ane is called elemen a y i and only i i con ains no inne
memb ane) o dele e Bby he ule (1, DR[B], in3). Wi h he s ing a2na i ing
in memb ane 3, we ge Ba2nin memb ane 1 by he ule (3, IL[B], ou ). Now we
double he numbe o symbols aby applying he sequence o ules (1, DR[a], in2)
and (3, IL[aa], ou ) 2n imes, finally ob aining a2n+1 B. Hence, in sum we ge
L(Π) = {a2n|n≥0} o he language gene a ed by his P sys em µo ype
D1
RI2
L.
130 R. F eund, Y. Rogozhin, S. Ve lan
3 Compu a ional Comple eness o P Sys ems wi h Minmal
Subs i u ion Rules
In his sec ion we conside se e al a ian s o P sys ems wi h subs i u ion ules
o minimal size, he main esul showing compu a ional comple eness o simple
P sys ems wi h ules o ype D1I1. Ye fi s we show ha o any ecu si ely
enume able language we can cons uc a P sys em, wi h he heigh o he ee
s uc u e being only 1 (which is he minimum possible acco ding o Theo em 1),
o ype D1
RI1
LS1
R, i.e., using minimal igh inse ions and minimal igh dele ions
and mu a ions (subs i u ions).
Theo em 4. L(D1
RI1
LS1
R-LP⟨1⟩)=RE.
P oo . F om Theo em 2 we know ha L(PSZNF) = RE, hence, we will only
show ha o e e y Pos sys em G= (V, T, A, P) in Z-no mal o m we a e able
o cons uc equi alen P sys em Πo ype D1
RI1
LS1
R. We assume ha he ules
in Pa e labelled in a unique way by labels om a fini e se Lab wi h 1 /∈Lab
and z∈Lab. We now cons uc a P sys em Π,Π= (G′, µ, R, 1), wi h a fla
ee s uc u e µo heigh 1, i.e., wi h he ou e mos memb ane ( he so-called skin
memb ane) being labelled by 1, and all he o he memb anes being elemen a y
memb anes inside he skin memb ane being labelled by labels om
Lab′={1,#} ∪ {l|l:p∈Lab}
∪{¯
h|h:P[ah/bhch]∈P}∪{¯
h|h:P[ahbh/ch]∈P}.
G′= (V′, T, A, P′), V′={x, ¯xl|x∈V, l ∈Lab}∪ {#}, and P′con ains he
minimal le inse ion, igh dele ion, and igh subs i u ion ules con ained in he
ules o Ras lis ed in he ollowing:
h:P[ahbh/ch]: (1, DR[bh], inh), (h, SR[ah/¯ah
h], ou ), (h, IL[#] , ou ),
(1, DR[¯ah
h], in¯
h),(¯
h, IL[ch], ou );
h:P[ah/bhch]: (1, SR[ah/¯ah
h], inh), (h, IL[ch], ou ),
(1, DR[¯ah
h], in¯
h),(¯
h, IL[bh], ou );
h:P[ah/bh]: (1, DR[ah], inh), (h, IL[bh], ou );
h:P[ah/λ]: (1, SR[ah/ah], inh), (l, DR[ah], ou ), o ah=Z;
z:P[Z/λ]: (DR[Z], inz);
he addi ional memb ane # is used o ap all compu a ions no leading o a
e minal s ing in an infini e loop by he ules (1, IL[#] , in#) and (#, IL[#] , ou );
o his pu pose, he ule (h, IL[#] , ou ) is used in case o h:P[ahbh/ch], oo.
Due o he ea u es o he unde lying Pos sys em in Z-no mal o m, all e minal
s ings om L(G) can be ob ained as final esul s o a hal ing compu a ion in he
elemen a y memb ane z, whe eas all o he possible compu a ions in Πne e hal ,
finally being apped in an infini e loop gua an eed by he ules leading in o and
ou om memb ane #. Hence, in sum we ge L(Π) = L(G).
Summa izing he esul s o Theo ems 1 and 4, we ge :
P Sys ems wi h Minimal Le and Righ Inse ion and Dele ion 131
Co olla y 1. L(D1I1S1)=L(D1I1S1-LP⟨0⟩)⊂REG ⊂
L(D1
RI1
LS1
R-LP⟨n⟩)=RE o all n≥1.
I we wan o es ic ou sel es o he simple a ge s he e, in, ou , hen we ha e
o use a mo e difficul p oo echnique han in he p oo o Theo em 4.
Theo em 5. L(D1I1-LsP⟨8⟩)=RE.
P oo . In o de o show he inclusion RE ⊆ L (D1I1-LsPLsP⟨8⟩), as in he p oo
o Theo em 4 we s a om a Pos sys em G= (V, T, A, P) in Z-no mal o m wi h
assuming he ules in P o be labelled in a unique way by labels om a fini e se
Lab wi h 1 /∈Lab and z∈Lab and cons uc an equi alen simple P sys em Π,
Π= (G′, µ, R, 1), o ype D1I1, wi h G′= (V′, T, A, P ′) and
V′=V∪VR∪ {S},VR={D, E, F, H, J, K, M},
P′={+X, −X|X∈V∪ {S}} ∪ {X+, X− | X∈V∪VR},
as ollows: The memb ane s uc u e µconsis s o he skin memb ane 1 as well
as o linea s uc u es needed o he simula ion o he ules in G: Fo e e y ule
h:P[ahbh/ch] and e e y ule h:P[ah/bhch] in Pwe need a linea s uc u e o
8 memb anes [(h,1) [(h,2) ... [(h,8) ](h,8) ...](h,2) ](h,1) and o e e y ule h:P[ah/bh]
and e e y ule h:P[ah/λ] in Pwe need a linea s uc u e o 6 memb anes
[(h,1) [(h,2) ... [(h,6) ](h,6) ...](h,2) ](h,1) ; mo eo e , o ge ing he e minal esul s, we
need he linea s uc u e o 3 memb anes [(z,1) [(z,2) [(z,3) ](z,3) ](z,2) ](z,1) .
The simula ions o he o he ules om Pa e accomplished by he p ocedu es
as shown in he ables below, whe e he columns ha e o be in e p e ed as ollows:
in he fi s column, he memb ane (label) his lis ed, in he second one only he
ule p∈Pis gi en, which in o al desc ibes he ule (h, p, in)∈R, whe eas he
ule pin he fi h column has o be in e p e ed as he ule (h, p, ou )∈R.; he
s ings in he hi d and he ou h column lis he s ings ob ained when going up
in he linea memb ane s uc u e wi h he ules (h, p, in) om column 2 and going
down wi h he ules (h, p, ou ) om column 5, espec i ely. The symbol Fcanno
be e ased anymo e, hence, whene e Fhas been in oduced, a some momen , he
compu a ion will land in an infini e loop wi h only in oducing mo e and mo e
symbols F. The main idea o he p oo is ha we choose he memb ane o go in o
by he ule (1, K+, in) in a non-de e minis ic way. The goal is o each he e minal
memb ane (z, 3) s a ing wi h a s ing wZ,w∈T∗, in he skin memb ane:
(z, 3) w
(z, 2) Z−wZ F+
(z, 1) K−wZK wF F+
1K+wZ wFF
Ge ing he e minal s ing w∈T∗
The ables below a e o be in e p e ed in he same way as abo e; ye now
we only lis he esul s o co ec simula ions in column 4 and omi he esul s o
adding he ap symbol F. Mo eo e , he ule D−in he skin memb ane is he only
one in he whole sys em which uses he a ge he e, i.e., i has o be in e p e ed
as (1, D−, he e).