1
Ve i ying a P sys em gene a ing squa es
Ma io J. P´
e ez-Jim´
enez
Fe nando Sancho-Capa ini
Dp o. Ciencias de la Compu aci´
on e In eligencia A i icial
Uni e sidad de Se illa, Espa˜
na
Ma io.Pe ez,Fe nando.Sancho
g
@cs.us.es
Abs ac . In [1], an example o a P sys em gene a ing exac ly all he squa es o na u al numbe s
g ea e han 1 is gi en. Ne e heless, only an in o mal easoning o his esul is p esen ed. In his
pape we s udy a simila P sys em o i (only one e olu ion ule is modi ied). A o maliza ion o
he syn ax o he P sys em ollowing [3] is gi en, and we s a e he e i ica ion o he gi en P sys em
h ough soundness and comple eness: (a) e e y success ul compu a ion o he P sys em gene a e a
squa e g ea e o equal o 1 (soundness); (b) e e y na u al numbe g ea e o equal o 1 is he ou pu
o a success ul compu a ion o he sys em (comple eness). Then we es ablish he o mal e i ica ion
h ough he s udy o he c i ical poin s o he compu a ions o he P sys em ha gi e o us impo an
in o ma ion o cha ac e ize he success ul compu a ions.
1. In oduc ion
In Oc obe 1998, Gheo ghe P˘aun ([1]) in oduces a new compu abili y model, o a dis ibu ed pa allel
ype, based on he no ion o memb ane s uc u e. This model, called ansi ion P sys em, s a om he
obse a ion ha he p ocesses which ake place in he complex s uc u e o a li ing cell can be conside ed
compu a ions. Following [1], we can conside he P sys ems as de ices which gene a e numbe s: he sum
o mul iplici ies o objec s in he ou pu memb ane is he gene a ed numbe .
In [1], he ollowing P sys em, whe e 4 memb ane is he ou pu one. Also, i is said ha he se o
na u al numbe s gene a ed by he abo e P sys em is
N
() =
n
2
:
n

1
g
.
2M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es
4
3
2
1
a
a
a
a b’
b’δ
b’
b
b
b
( c , in )
4
a δ
>
P sis ema Π
This pape is s uc u ed in he ollowing way. In sec ion 2 some p elimina ies abou o maliza ion o
ansi ion P sys ems is p esen ed, ollowing [3]. In sec ion 3 he o mal syn ax, ollowing sec ion 2, o

is gi en. In sec ion 4 cha ac e iza ions o success ul compu a ions o abo e P sys em is es ablished. In
sec ion 5 we show ha he ou pu o e e y success ul con igu a ion o

encodes he squa e o a na u al
numbe g ea e han 1 (soundness o he P sys em) and, also ha he squa e o e e y na u al numbe
g ea e han 1 is gene a ed by some success ul compu a ion o

(comple eness o he P sys em).
2. P elimina ies abou ansi ion P sys ems
Following [3], a memb ane s uc u e is a oo ed ee, whe e he nodes a e called memb anes, he oo is
called skin, and he lea es a e called elemen a y memb anes. Usually, we ep esen a oo ed ee by an
o de ed pai such ha he i s componen o he pai is he oo o he ee and he second componen
is he adjacency lis ha consis s o
n
lis , one o each e ex
i
. The lis o e ex
i
con ains jus hose
e ices adjacen om
i
.
Acell
(
o supe -cell
)
o e an alphabe ,
A
, is a pai
(
; M
)
, whe e

= (
V
(

)
; E
(

))
is a memb ane
s uc u e (we conside
E

(

)
as ollows:
(
x; y
)
2
E

(

)
()
y
is a child o
x
in

), and
M
is an
applica ion,
M
:
V
(

)
!
M
(
A
)
( he se o mul ise s o e
A
).
Le
(
; M
)
a cell o e an alphabe ,
A
. Le
x
2
V
(

)
. An e olu ion ule associa ed o
x
is a 3- uple
= (
~
d
; ~
; Æ
)
whe e
~
d
is a mul ise o e
A
;
~
is a unc ion wi h domain
V
(

)
[
he e; ou
g
and
ange con ained in
M
(
A
)
whe e
he e; ou =
2
V
(

)
(he e
6
=
ou ); and
Æ
2 :
Æ; Æ
g
, wi h
:
Æ; Æ =
2
A
(
:
Æ
6
=
Æ
).
Acollec ion
R
o e olu ion ules associa ed o
C
is a unc ion wi h domain
V
(

)
such ha o e e y
memb ane
x
2
V
(

)
,
R
x
=
x
1
;::: ;
x
s
x
g
is a ini e se (possibly emp y) o (e olu ion) ules associa ed
o
x
. A p io i y ela ion o e
R
is a unc ion,

, wi h domain
V
(

)
such ha o e e y memb ane
x
2
V
(

)
,

x
is a s ic pa ial o de o e
R
x
(possibly emp y).
A ansi ion P-sys em is a 4- uple
 = (
A; C
0
;
R
; i
0
)
, whe e
A
is a non-emp y ini e se (usually
called base alphabe );
C
0
= (

0
; M
0
)
is a cell o e
A
;
R
is an o de ed pai
(
R; 
)
whe e
R
is a collec ion
o (e olu ion) ules associa ed o
C
0
, and

is a p io i y ela ion o e
R
; and
i
0
is a node o

0
, which
speci ies he ou pu memb ane o

.
M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es 3
Acon igu a ion,
C
, o a P sys em,
=(
A; C
0
;
R
; i
0
)
wi h
C
0
= (

0
; M
0
)
, is a cell
C
= (
; M
)
o e
A
, whe e
V
(

)

V
(

0
)
, and

has he same oo as

0
. The con igu a ion
C
0
will be called he
ini ial con igu a ion o

. Le
x
2
V
(

0
)
. We say ha he (e olu ion) ule
2
R
x
is semi-applicable o
C
i : (a) he memb ane associa ed o node
x
exis s in
C
, ha is,
x
2
V
(

)
; (b) dissolu ion is no allowed
in oo node, ha is, i
x
is he oo node o

, hen
Æ
=
:
Æ
; (c) he memb ane associa ed o
x
has all
he necessa y objec s o apply he ule, ha is,
~
d

M
(
x
)
; and (d) nodes whe e he ule ies o send
objec s (by means o
in
y
) a e child en o
x
, ha is,
8
y
2
V
(

)(
~
(
y
)
6
=
~
0
!
(
x; y
)
2
E

(

))
.
We say ha he ule
2
R
x
is applicable o
C
, i i is semi-applicable o
C
and he e is no semi-
applicable ules in
R
x
wi h highe p io i y. Tha is:
:9
0
(
0
2
R
x
^

x
(
0
;
)
^
0
semi-applicable o
C
)
.
We will say ha
~p
2
N
N
is an applicabili y ec o o e
x
2
V
(

)
o
C
, and we will deno e i as
~p
2
Ap
(
x; C
)
, i :(a) he node is s ill ali e, ha is,
~p
6
=
~
0
)
x
2
V
(

)
; (b) i has co ec size, ha is,
8
j
(
j > s
x
!
~p
(
j
) = 0)
, (whe e
s
x
is he numbe o ules associa ed o
x
); (c) e e y ule can be applied
as many imes as he ec o
~p
indica es, ha is,
8
j
(1

j

s
x
!
~p
(
j
)

N
Ap
(
x
j
; C; x
))
; (d) all he
ules can be applied simul aneously, ha is,
P
s
x
j
=1
~p
(
j
)

~
d
x
j

M
(
x
)
; and (e) i is maximal, ha is,
:9
~
2
N
N
(
~p < ~
^
~
2
Ap
(
x; C
))
.
We will say ha
P
:
V
(

0
)
!
N
N
is an applicabili y ma ix o e
C
, deno ed
P
2
M
Ap
(
C
)
, i
o e e y
x
2
V
(

0
)
we ha e ha
P
(
x
)
2
Ap
(
x; C
)
. We de ine
(
P ; C
) =
x
:
x
2
V
(

)
^ 9
j
(1

j

s
x
^
P
x
(
j
)
6
= 0
^
Æ
x
j
=
Æ
)
g
I
P
is an applicabili y ma ix o e
C
= (
; M
)
and
V
(

) =
i
1
;::: ;i
k
g
, hen we deno e
P
=
((
p
i
1
1
; : : : ; p
i
1
s
i
1
)
;::: ;
(
p
i
k
1
;::: ;p
i
k
s
i
k
))
.
Fo each node
x
2
V
(

)
, we de ine he dono s o
x
o
C
in he applica ion o
P
as ollows:
D on
(
x; P ; C
) =
8
>
<
>
:
;
;
i
x
2
(
P ; C
)
y
2
V
(

) :
y
2
(
P ; C
)
^
x

y
^
^ 8
z
2
V
(

)(
x

z

y
!
z
2
(
P ; C
))
g
;
i
x =
2
(
P ; C
)
We de ine he execu ion o
P
o e
C
, deno ed
P
(
C
)
, as he con igu a ion o

,
C
0
= (

0
; M
0
)
,
whe e:


0
is he oo ed ee ob ained om

by means o :
–
V
(

0
) =
V
(

)

(
P ; C
)
–I
x; y
2
V
(

0
)
, hen:
(
x; y
)
2
E

(

0
)
, 9
x
0
; : : : ; x
n
2
V
(

)(
x
1
;::: ;x
n

1
2
(
P ; C
)
^
x
0
=
x
^
x
n
=
y
^ 8
i
(0

i < n
!
(
x
i
; x
i
+1
)
2
E

(

)))

M
0
(
x
) =
8
>
<
>
:
M
00
(
x
)
[
[
y
2
D on
(
x;P ;C
)
M
00
(
y
)
;
i
x =
2
(
P ; C
)
;
;
i
x
2
(
P ; C
)
We will say ha a con igu a ion
C
1
o a
P
sys em

yields a con igu a ion
C
2
by a ansi ion in
one s ep o

, deno ed
C
1
)

C
2
, i he e exis s a non–ze o applicabili y ma ix o e
C
1
,
P
, such ha
P
(
C
1
) =
C
2
.
4M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es
The compu a ion ee o a
P
sys em

, deno ed
Comp
()
, is a oo ed labeled maximal ee de ined
as ollows: he oo o he ee is he ini ial con igu a ion,
C
0
, o

. The child en o a node a e he
con igu a ions ha ollow in one s ep o ansi ion. Nodes and edges a e labeled by con igu a ions and
applicabili y ma ices, espec i ely, in such way ha wo labeled nodes
C; C
0
a e adjacen in
Comp
()
,
by means an edge labeled wi h
P
, i and only i
P
2
M
Ap
(
C
)

0
g ^
C
0
=
P
(
C
)
. The maximal
b anches o
Comp
()
will be called compu a ions o

. We will say ha a compu a ion o

hal s i i
is a ini e b anch. The con igu a ions e i ying
M
Ap
(
C
) =
0
g
will be called hal ing con igu a ions.
We say ha a compu a ion
C 
C
0
)

C
1
)

:::
)

C
n
o a
P
sys em
 = (
A; C
0
;
R
; i
0
)
is
success ul i his compu a ion hal s and
i
0
is a lea o he oo ed ee

n
, whe e
C
n
= (

n
; M
n
)
. Then
we will say ha con igu a ion
C
n
is success ul, and
n
is he leng h o
C
. The nume ical ou pu o a
success ul compu a ion,
C
, is
O
(
C
) =
j
M
C
n
(
i
0
)
j
whe e
C
n
is he success ul con igu a ion o
C
. The
ou pu o a
P
sys em

is
O
() =
O
(
C
) :
C
is a success ul compu a ion o

g
.
Le
 = (
A; C
0
;
R
; i
0
)
a
P
sys em. The se o na u al numbe s gene a ed by

, deno ed
N
()
, is
de ined as ollows:
N
() =
O
(
C
) :
C
is a success ul compu a ion o

g
.
3. Fo maliza ion o he syn ax o he P sys em

Nex , we a e going o o malize he syn ax o he P sys em

, ollowing he de ini ions o abo e sec ion.
The P sys em

is a 4– uple
(
A; C
0
;
R
; i
0
)
, whe e:
(a) The base alphabe is
A
=
a; b; b
0
; ;
g
.
(b) The ini ial con igu a ion,
C
0
= (

0
; M
0
)
, is de ined as ollows:

0
= (1
;
((1
;
2)
;
(2
;
1
;
3
;
4)
;
(3
;
2)
;
(4
;
2)))
Tha is,

0
is he memb ane s uc u e gi en by means o he ollowing oo ed ee:
1
2
43
M
0
is he applica ion om
1
;
2
;
3
;
4
g
o
M
(
A
)
de ined as:
M
0
(1) =
M
0
(2) =
M
0
(4) =
;
y
M
0
(3) =
a
g
.
(c)
R
= (
R; 
)
, whe e:

R
is a collec ion o ules associa ed o
C
0
; ha is,
R
is an applica ion wi h domain in
1
;
2
;
3
;
4
g
, de ined as:
R
(1) =
R
(4) =
;
,
R
(2) =
2
1
;
2
2
;
2
3
;
2
4
g
y
R
(3) =
3
1
;
3
2
;
3
3
g
,
whe e:
–
2
1
= (
d
2
1
;
2
1
; Æ
2
1
)
, wi h
d
2
1
=
b
0
g
,
2
1
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
2
1
(1) =
2
1
(2) =
2
1
(3) =
2
1
(4) =
2
1
(
ou
) =
;
;
2
1
(
he e
) =
b
g
, and, also,
Æ
2
1
=

Æ
.
M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es 5
–
2
2
= (
d
2
2
;
2
2
; Æ
2
2
)
, wi h
d
2
2
=
b
g
,
2
2
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en as
2
2
(1) =
2
2
(2) =
2
2
(3) =
2
2
(
ou
) =
;
;
2
2
(4) =

g
;
2
2
(
he e
) =
b
g
, and also,
Æ
2
2
=

Æ
.
–
2
3
= (
d
2
3
;
2
3
; Æ
2
3
)
, wi h
d
2
3
=
g
,
2
3
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
2
3
(1) =
2
3
(2) =
2
3
(3) =
2
3
(4) =
2
3
(
ou
) =
;
;
2
3
(
he e
) =
g
, and, also,
Æ
2
3
=

Æ
.
–
2
4
= (
d
2
4
;
2
4
; Æ
2
4
)
, wi h
d
2
4
=
g
,
2
4
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
2
4
(1) =
2
4
(2) =
2
4
(3) =
2
4
(4) =
2
4
(
ou
) =
;
;
2
4
(
he e
) =
a
g
, and, also,
Æ
2
4
= +
Æ
.
–
3
1
= (
d
3
1
;
3
1
; Æ
3
1
)
, wi h
d
3
1
=
a
g
,
3
1
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
3
1
(1) =
3
1
(2) =
3
1
(3) =
3
1
(4) =
3
1
(
ou
) =
;
;
3
1
(
he e
) =
ab
0
g
, and, also,
Æ
3
1
=

Æ
.
–
3
2
= (
d
3
2
;
3
2
; Æ
3
2
)
, wi h
d
3
2
=
a
g
,
3
2
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
3
2
(1) =
3
2
(2) =
3
2
(3) =
3
2
(4) =
3
2
(
ou
) =
;
;
3
2
(
he e
) =
b
0
g
, and, also,
Æ
3
2
= +
Æ
.
–
3
3
= (
d
3
3
;
3
3
; Æ
3
3
)
, wi h
d
3
3
=
g
,
3
3
:
1
;
2
;
3
;
4
g [
he e; ou
g !
M
(
A
)
gi en
as
3
3
(1) =
3
3
(2) =
3
3
(3) =
3
3
(4) =
3
3
(
ou
) =
;
;
3
3
(
he e
) =
g
, and, also,
Æ
3
3
=

Æ
.


is he applica ion wi h domain in
1
;
2
;
3
;
4
g
de ined as:

(1) =

(3) =

(4) =
;
and

(2) =
(
3
2
;
4
2
)
g
.
(d) The ou pu memb ane is
i
0
= 4
.
4. Cha ac e izing success ul con igu a ions o

Le

be a P sys em designed o gene a e a se
B
o na u al numbe s. To es ablish he e i ica ion o

in
ela ion o he se
B
, a p edica e o e con igu a ions ( ha is, o e
C omp
()

N
), being, in some way,
an in a ian o he whole p ocess o gene a ion o he P sys em

, is sea ched. Tha is, his p edica e will
be ue o e e y compu a ion,
C
, o

and e e y na u al numbe . Also, he u h o he p edica e o e all
he con igu a ions o

mus ex ac impo an in o ma ion o es ablish he soundness and comple eness
o

ela ed o he gene a ion o he se
B
.
The p ocess o e i ica ion o a P sys em,

, is based on he analysis o he con en o e e y
memb ane in e e y compu a ion ha can be ob ained in

. Gi en a compu a ion,
C
, o

, we will
deno e
C
0
)

C
1
)

:::
)

C
k
)

:::
. Tha is,
C
k
ep esen s he con igu a ion ob ained a -
e he execu ion o
k
s eps in he compu a ion
C
. In a na u al way, a pa ial unc ion,
STEP
:
C omp
()

N

V
(

0
)
 !
M
(
A
)
, can be de ined o assign o e e y compu a ion
C
, o

, e e y
na u al numbe
k
and e e y memb ane
i
o he P sys em, he con en o he memb ane
i
a e he execu-
ion o
k
s eps in he compu a ion
C
. I , a e he execu ion o he
k
- h s ep, he memb ane
i
is dissol ed,
hen
STEP
(
C
; k ; i
)
is no de ined, in his case, we will deno e
STEP
(
C
; k ; i
)
"
. In o he case, we will
deno e
STEP
(
C
; k ; i
)
#
. In gene al, we will deno e
STEP
(
C
; k ; i
) =
C
k
(
i
)
. We deno e
jC j
he leng h
o he compu a ion
C
ha , e en ually, can be in ini e.

6M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es
De ini ion 4.1. Fo e e y memb ane,
i
, and e e y compu a ion
C
o

, we de ine
Æ
(
C
; i
) = min
m
:
C
m
(
i
)
"g
Ha ing in mind ha no memb ane is dissol ed in he ini ial con igu a ion o a e e y P sys em

, we
ha e ha
Æ
(
C
; i
)

1
, o e e y
C 2
C omp
()
and e e y memb ane
i
o

.
Gi en a P sys em

and a memb ane
i
o

, we can de ine in a na u al way a pa ial unc ion
D
i
:
C omp
()
 !
N

0
g
, as ollows:
D
i
(
C
) =
Æ
(
C
; i
)
. Tha is,
D
i
assign o e e y compu a ion
C
o

a na u al numbe ep esen ing he ins an whe e he memb ane
i
o

is dissol ed (i any).
To es ablish ha he conside ed P sys em

gene a es he se
n
2
:
n

1
g
, wewill y o cha ac e ize
he success ul compu a ions o

.
Fo ha , i s we will gi e a p edica e o e he con igu a ions o

o be an in a ian along he
execu ion o he P sys em

. Le us conside he o mula

(
C
; n
)

(
n < Æ
(
C
;
3)
! C
n
= (

0
;
(
;
;
;
; ab
0
n
2
n
;
;
)))
^
(
n
=
Æ
(
C
;
3)
! C
success.
^
O
(
C
) =
n
2
)
To make easie he p oo s, and ollowing sec ion 2, he applicabili y ec o will be exp essed wi h a
ini e numbe o componen s (so many as ules he memb ane has). We will deno e by
0
he ec o wi h
all null componen s, no a ending he size o i .
I
C
= (
; M
)
is a cell, whe e
V
(

) =
a
1
;::: ;a
n
g 
N
wi h
a
1
<

< a
n
, we will no e
M
= (
M
(
a
1
)
;::: ;M
(
a
n
))
. Fo simplici y o no a ion, we will ep esen he mul ise s by means o he
associa ed wo d, and
;
will be he emp y mul ise .
Fi s , we a e going o de e mine e e y con igu a ion o he P sys em be o e memb ane 3 is dissol ed.
P oposi ion 4.1. Fo e e y compu a ion
C
o

we ha e:
8
n
(
n < Æ
(
C
;
3)
! C
n
= (

0
;
(
;
;
;
; ab
0
n
2
n
;
;
)))
P oo :
Le
C
be a compu a ion o

. Le us p o e he esul by induc ion on
n
. Fo he base case,
n
= 0
, i is
enough o conside ha
Æ
(
C
;
3)

1
and
C
0
= (

0
;
(
;
;
;
; a ;
;
))
.
Le
n
2
N
such ha
(
n < Æ
(
C
;
3)
! C
n
= (

0
;
(
;
;
;
; ab
0
n
2
n
;
;
))
. I
n
+ 1
< Æ
(
C
;
3)
hen
n <
Æ
(
C
;
3)
and, hence,
C
n
= (

0
;
(
;
;
;
; ab
0
n
2
n
;
;
))
. As
C
n
+1
(3)
#
, we deduce ha he con igu a ion
C
n
+1
is
ob ained om
C
n
applying he ma ix
~p
= (
0
;
0
;
(1
;
0
;
2
n
)
;
0
)
(applicabili y ma ix o e
C
n
), since no dis-
solu ion is applied o e memb ane 3. The, we ha e ha
C
n
+1
=
~p
(
C
n
) = (

0
;
(
;
;
;
; ab
0
(
n
+1)
2
n
+1
;
;
))
.
u
Nex , we will p oo ha a c i ical poin o he compu a ions o he P sys em

is in he ins an when
he memb ane 3 is dissol ed. Tha is, we will jus i y ha knowing when memb ane 3 is dissol ed is
impo an o cha ac e ize he success ul compu a ions o

.
P oposi ion 4.2. Fo e e y compu a ion
C
o he P sys em

such ha
n
=
Æ
(
C
;
3)
<
1
, we ha e:
1.
C
n
= (

0
;
(
;
; b
0
n
2
n
;
;
))
, whe e

0
= (1
;
((1
;
2)
;
(2
;
1
;
4)
;
(4
;
2)) )
.
2. Fo e e y
k
such ha
0

k

n

1
, we ha e ha
C
n
+1+
k
= (

0
;
(
;
; b
n
2
n

k

1
; 
k n
))
, whe e

0
is as abo e.
3.
C
2
n
+1
= (

00
;
(
ab
n
; 
n
2
))
, whe e

00
= (1
;
((1
;
4)
;
(4
;
1)))
.
M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es 7
4. The compu a ion
C
is success ul, i s leng h is
jC j
= 2
n
+ 1
, and, also, he nume ical ou pu o his
compu a ion is
O
(
C
) =
n
2
.
P oo :
1. I
n
=
Æ
(
C
;
3)
<
1
hen
0

n
1
< Æ
(
C
;
3)
. F om p oposi ion 4.1, we deduce ha
C
n
1
=
(

0
;
(
;
;
;
; ab
0
(
n

1)
2
n

1
;
;
))
. Ha ing in mind ha
Æ
(
C
;
3) =
n
, we ob ain ha he con igu a ion
C
n
is ob ained om
C
n

1
execu ing he applicabili y ma ix
~p
= (
0
;
0
;
(0
;
1
;
2
n

1
)
;
0
)
o e
C
n

1
.
Hence,
C
n
=
~p
(
C
n

1
)=(

0
;
(
;
; b
0
n
2
n
;
;
))
, whe e

0
= (1
;
((1
;
2)
;
(2
;
1
;
4)
;
(4
;
2)) )
.
2. Le us p o e by induc ion on
k
. Fo he base case,
k
= 0
, le us obse e ha om (1) we ob ain
ha
C
n
= (

0
;
(
;
; b
0
n
2
n
;
;
))
. In his si ua ion, since
n

1
, i is possible o apply he ule
2
3
o he
memb ane 2 and hen, by he s ong sense in which he p io i y is in e p e ed, he ule
2
4
can no
be applied o
C
n
( his ule would dissol e he memb ane 2). Hence, he only ma ix applicabili y
o e
C
n
will be
~p
= (
0
;
(
n;
0
;
2
n

1
;
0)
;
0
)
. In consequence,
C
n
+1
=
~p
(
C
n
)=(

0
;
(
;
; b
n
2
n

1
;
;
))
.
Le
k
be such ha
0

k < n

1
, and le us suppose ha
C
n
+1+
k
= (

0
;
(
;
; b
n
2
n

k

1
; 
k n
))
.
Since
n

k

1
>
0
, we deduce ha i is possible o apply he ule
2
3
o memb ane 2 and hen,
he only applicabili y ma ix o e
C
n
+1+
k
is
~p
= (
0
;
(0
; n;
2
n

k

2
;
0)
;
0
)
. Hence, we ha e ha
C
n
+1+
k
+1
= (

0
;
(
;
; b
n
2
n

k

2
;
(
k
+1)
n
))
3. By applying (2) o he case
k
=
n

1
, we ob ain ha
C
2
n
= (

0
;
(
;
; b
n
; 
(
n
1)
n
))
.
Then, he only applicabili y ma ix o e
C
2
n
is
~p
= (
0
;
(0
; n;
0
;
1)
;
0
)
. Hence, we ha e ha he
con igu a ion
C
2
n
+1
= (

00
;
(
ab
n
; 
n
2
))
, whe e

00
= (1
;
((1
;
4)
;
(4
;
1)))
.
4. F om (3) we deduce ha
C
2
n
+1
= (

00
;
(
ab
n
; 
n
2
))
. Ha ing in mind ha
V
(

00
) =
1
;
4
g
and
R
1
=
R
4
=
;
we deduce ha
M
Ap
(
C
2
n
+1
) =
(
0
;
0
)
g
. Then he con igu a ion
C
2
n
+1
is a hal ing
con igu a ion. Also, since
4
2
V
(

00
)
and 4 is a lea o

00
esul s ha he con igu a ion
C
2
n
+1
is
success ul. Hence, he compu a ion
C
is success ul, i s leng h is
2
n
+ 1
, and i s nume ical ou pu
is
O
(
C
) =
jC
2
n
+1
(4)
j
=
n
2
.
u
As a i s consequence om his p oposi ion, le us see ha a e he ins an he memb ane 3 is
dissol ed, he P sys em e ol es in a “de e minis ic” way.
Co olla y 4.1. Fo e e y
n

1
and e e y
C
;
C
0
2
C omp
()
such ha
n
=
Æ
(
C
;
3) =
Æ
(
C
0
;
3)
we ha e
ha
8
k
(
n

k

2
n
+ 1
! C
k
=
C
0
k
)
.
P oo :
The case
k
=
n
ollows om (1) in abo e p oposi ion, he case
n < k

2
n
ollows om (2), and he
case
k
= 2
n
+ 1
ollows om (3).
u
Nex , le us see ha i wo compu a ions ha e he same ins an o dissolu ion o memb ane 3, hen hese
compu a ions a e equal.
8M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es
Co olla y 4.2. Fo e e y
n

1
and e e y
C
;
C
0
2
C omp
()
such ha
n
=
Æ
(
C
;
3) =
Æ
(
C
0
;
3)
we ha e
ha
C
=
C
0
.
P oo :
Le
n

1
and
C
;
C
0
2
C omp
()
such ha
n
=
Æ
(
C
;
3) =
Æ
(
C
0
;
3)
. By applying (4) in p oposi ion 4.2,
and abo e co olla y, i ’s enough o p o e ha
8
k
(0

k

n

1
! C
k
=
C
0
k
)
. Bu , his las ela ion
ollows di ec ly om p oposi ion 4.1.
u
Co olla y 4.3. The e exis s, a mos , a compu a ion o

no o be success ul.
P oo :
Le
C
be a compu a ion o

no o be success ul. F om p oposi ion 4.2 we deduce ha
8
k
(
k < Æ
(
C
;
3))
.
Hence, om p oposi ion 4.1 esul s ha
C
k
= (

0
;
(
;
;
;
; ab
0
k
2
k
;
;
)))
. Then,
C
is unique.
u
Nex , le us see ha he o mula

(
C
; n
)
is ue o e e y con igu a ion
C
n
o he P sys em

.
Co olla y 4.4. The o mula

(
C
; n
)
is an in a ian o he P sys em

. Tha is,
8C 2
C omp
()
8
n
2
N
(

(
C
; n
))
.
P oo :
I ollows di ec ly om p oposi ion 4.1 and (4) in p oposi ion 4.2.
u
Nex , we a e going o cha ac e ize he success ul compu a ions o

h ough he ins an he mem-
b ane 3 is dissol ed.
Co olla y 4.5. Le
C
be a compu a ion o

. The ollowing a e equi alen s:
(a)
C
is a success ul compu a ion.
(b)
Æ
(
C
;
3)
<
1
.
(c)
Æ
(
C
;
3)
<
1
and
jC j
= 2

Æ
(
C
;
3) + 1
.
P oo :
Le
C
be a success ul compu a ion. Le
k
=
jC j
. Then
1

k <
1
. Le us see ha
Æ
(
C
;
3)

k
. In
o he case, om p oposi ion 1 we ha e ha
C
k
= (

0
;
(
;
;
;
; ab
0
k
2
k
;
;
))
. Which con adic s
k
=
jC j
,
since om he exis ence o no null applicabili y ma ix o e
C
k
( o example,
~p
= (
0
;
0
;
(1
;
0
;
2
k
)
;
0
)
)
we would ha e ha
C
k
is no a hal ing con igu a ion.
I
Æ
(
C
;
3)
<
1
hen, om (4) in p oposi ion 4.2, esul s ha
jC j
= 2
n
+ 1
. Finally,
(

)
)
(
a
)
esul s
di ec ly om (4) in p oposi ion 4.2.
u
M.J. P´e ez-Jim´enez, F. Sancho-Capa ini /Ve i ying a P sys em gene a ing squa es 9
5. Soundness and Comple eness o he
P
sys em

To es ablish ha he se o na u al numbe s gene a ed by

is
N
() =
n
2
:
n

1
g
we mus o p o e
wo esul s:

The nume ical ou pu o any success ul compu a ion o he P sys em

encodes he squa e o a
na u al numbe g ea e o equal o 1 (soundness o he P sys em).

Fo e e y
n

1
he e exis s, a leas , a success ul compu a ion,
C
,o he P sys em

wi h nume ical
ou pu
O
(
C
) =
n
2
(comple eness o he P sys em).
Theo em 5.1.
(
Soundness
)
I
C
is a success ul compu a ion o he P sys em

, hen he e exis s
n

1
such ha he ou pu o
C
is
O
(
C
) =
n
2
.
P oo :
Le
C
be a success ul compu a ion o

. I
n
=
Æ
(
C
;
3)
hen, om co olla y 4.2, esul s ha
1

n <
1
.
Since he o mula

(
C
; n
)
is ue and
n
=
Æ
(
C
;
3)
, we deduce ha he compu a ion
C
is success ul and,
also,
O
(
C
) =
n
2
.
u
To es ablish he comple eness o

o gene a e he se
n
2
:
n

1
g
, we conside he o mula
'
(
n
)

9 C 2
C omp
() (
n
=
Æ
(
C
;
3))
. Le us see ha his o mula is ue o e e y na u al numbe g ea e o
equal o 1.
P oposi ion 5.1. Fo e e y na u al numbe
n

1
he e exis s a unique compu a ion,
C
, o

such ha
Æ
(
C
;
3) =
n
.
P oo :
Le us p o e he exis ence by induc ion on
n
. Fo he base case,
n
= 1
, he con igu a ion
C
1
, ob ained
om he ini ial con igu a ion,
C
0
, by applying he ma ix
~p
= (
0
;
0
;
(0
;
1
;
1)
;
0
)
(applicabili y ma ix
o e
C
0
), is conside ed. Since
3
2

a
!
b
0
Æ
, we ob ain ha
Æ
(
C
;
3) = 1
.
Le
n

1
and le us suppose he esul is ue o
n
. Le
C
be a compu a ion o

such ha
Æ
(
C
;
3) =
n
. F om p oposi ion 4.1, we deduce ha
C
n

1
= (

0
;
(
;
;
;
; ab
0
(
n

1)
2
n

1
;
;
)))
.
The se o applicabili y ma ices o e
C
n

1
is
M
Ap
(
C
n

1
) =
~p
1
; ~p
2
g
, whe e
~p
1
= (
0
;
0
;
(0
;
1
;
2
n

1
)
;
0
)
,
~p
2
= (
0
;
0
;
(1
;
0
;
2
n

1
)
;
0
)
Le
C
0
n
=
~p
2
(
C
n

1
)
. Then
C
0
n
= (

0
;
(
;
;
;
; ab
0
n
2
n
;
;
))
. Le
C
0
n
+1
=
~p
3
(
C
0
n
)
, whe e
~p
3
=
(
0
;
0
;
(0
;
1
;
2
n
)
;
0
)
, in his s ep memb ane 3 is dissol ed. Then
C
0
n
+1
= (

0
;
(
;
; b
0
(
n
+1)
2
n
+1
;
;
))
, whe e
he memb ane s uc u e is

0
= (1
;
((1
;
2)
;
(2
;
1
;
4)
;
(4
;
2)))
. Hence, he compu a ion
C
0
 C
0
)

C
1
)

:::
)

C
n

1
)

C
0
n
)

C
0
n
+1
)

:::
, e i ies ha
Æ
(
C
0
;
3) =
n
+ 1
.
Gi en
n

1
, he uniqueness o he compu a ion
C
e i ying
Æ
(
C
;
3) =
n
, ollows di ec ly om
co olla y 4.2.
u
P oposi ion 5.2. The e exis s an unique compu a ion,
C
, o

no o be success ul.