Laboratoire Bordelais de Recherche en Informatique
10 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Laboratoire Bordelais de Recherche en Informatique

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
10 Pages
English

Description

Niveau: Supérieur
Laboratoire Bordelais de Recherche en Informatique, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, 33 405 Talence Cedex, France. Rapport de Recherche Numéro 1135-96 Any Reversible Cellular Automaton Can be Represented with Block Permutations Jérôme Olivier Durand-Lose labri, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. Abstract Cellular Automata are mappings such that each cell is updated according to the states around it and a unique local function. Block Permutations are mappings that divide partitions regularly in rectangular blocks of states and make the same permutations on each block. We prove that any d-dimensional Reversible Cellular Automata (d-r-ca) can be expressed as the restriction of a composition of 2 d Block Permutations (bp). We exhibit such representation for any d-r-ca with 2 d bp of width 6r. We also give a construction with d+ 1 bp, but with width 3(d + 1)r. 1 Introduction Cellular Automata (ca) provide the most famous model for parallel phenomena, computations and architec- tures. They operate as iterative systems on d-dimensional innite arrays, the underlying space is Z d .

  • block permutation

  • old states

  • cellular automaton

  • all natural

  • over

  • unique local function

  • inverse block

  • any reversible


Subjects

Informations

Published by
Reads 11
Language English

Exrait

La
b
oratoire
B
oli
v
cells
ordelais
e
de
automaton
R
phenomenon
ec
In
herc
b
he
of
en
bri
I
famous
nformatique
v
ura
istory
cnrs
[8
1
blo
304,
P
Univ
the
ersit
Conjecture
Bordeaux
blo
I
image
351,
Rev
cours
w
de
though
la
the
Lib
full
ation
:
33
wing
405
ny
T
osition
alence
y
Cedex
ed
France
generalization
.
d
Rapp
.
ort
ulation
de
]
Rec
as
herc
i
he
jdu
Numo
of
1135-96
unique
An
(
y
nonissipativ
Rev
bac
ersible
Rev
Cellular
a
Automaton
computers
Can
1990
b
]
e
to
Represen
decidabilit
ted
large
with
mak
Blo
ra
c
:
k
automaton
P
as
erm
p
utations
a
Je
lattice
Olivier
to
Durandose
A

bp
l
erm
a
a
bri
]
,
dimensions
ura
2
cnrs
bp
1
end
304,
Conjecture
Univ
imensional
ersit
e
Bordeaux
osition
I

351,
x
cours
aux
de
y
la
the
Lib
b
ation
to
F
cal
405
Cellular
T
)
alence
mo
Cedex
systems
France
as
.
king
Abstract
its
Cellular
y
Automata
of
are
to
mappings
energy
suc
e
h
to
that
of
eac
Margolus
h
get
cell
tro
is
ra
up
aims
dated
:
according
and
to
y
the
article
states
the
around
ab
it
Conjecture
and
Conjecture
a
]
unique
el
lo
an
cal
esse
function
c
Blo
blo
c
mutations
k
k
P
imensional
erm
states
utations
d
are
partitioned
mappings
displa
that
c
divide
c
partitions
utation
regularly
is
in
a
rectangular
e
blo
suc
c
of
ks
Kari
of
v
states
1
and
and
mak
uses
e
the
the
for
same
the
p
t
erm
conjectures
utations
[6
on
:
eac
ny
h
el
blo
an
c
esse
k
c
W
2
e
p
pro
jdurand
v
ord
e
httpww
that
bor
an
/
y
d
d
the
imensional
of
Rev
states
ersible
neigh
Cellular
oring
Automata
according
(
a
d
lo
a
function
)
ersible
can
Automata
b
ra
e
are
expressed
for
as
deling
the
e
restriction
as
of
ell
a
for
comp
ktrac
osition
a
of
to
2
source
d
ersibilit
Blo
is
c
t
k
as
P
means
erm
sa
utations
e
(
in
bp
W
).
refer
W
reader
e
the
exhibit
article
suc
T
h
and
represen
[8
tation
to
for
a
an
in
y
duction
d
the
a
ld
with
,
2
uses
d
y
bp
:
of
)
width
a
6
bibliograph
r
.
.
this
W
they
e
e
also
follo
giv
conjecture
e
out
a
:
construction
1
with
,
d
8
+
1
1
A
bp
c
,
lular
but
c
with
b
width
expr
3(
d
d
a
+
omp
1)
of
r
ck
.
er
1
A
In
c
tro
is
duction
d
Cellular
arra
Automata
of
(
The
ca
Z
)
can
pro
e
vide
in
the
regularly
most
y
famous
blo
mo
ks
del
Blo
for
k
parallel
erm
phenomena
(
computations
)
and
a
arc
of
hitec
p
tures
utation
They
o
op
er
erate
h
as
partition
iterativ
Z
e
.
systems
[6
on
pro
d
es
imensional
Conj
inite
for
arra
1
ys
2
the
He
underlying
S
space
as
is
set
Z
states
d
the
.
during
Eac
sim
h
A
cell
the
tak
he
es
that
a
2
v
,
alue
5
from
3
a
A
ite
d
set
c
of
lular
states
c
S
b
.
expr
An
d
iteration
a
of
omp
a
of
ca
d
is
ck
the
ermutations
sync
eail
hronous
abr
replacemen
-b
t
eau
of
r
the
a
state
.u-
of
de
ev
r
ery

cell
ran
b
1In
[2
],
w
ck
blo
b
e
w
pro
y
v
2
e
V
Conj
v
1
v
for
x
an
function
y
new
dimension
1
with
[
2
o
d
other
+1
efore
1
mappings
bp
k
of
k
width
is
4
of
r
f
.
are
In
e
this
o
article
]
w
utation
e
k
pro
2
v
)
e
from
Conj
is
1
Permutation
for
Cellular
an
d
y
k
dimension
,
with
:
the
A
n
f
um
um
b
in
er
to
of
;
p
;
erm
on
utations
Blo
prop
y
osed
elemen
b
co
y
<
Kari
d
2
2
d
.
.
lengths
Our
width
constructiv
T
e
c
pro
div
of
+
is
:
based
h
on
.
the
ck
constructions
o
made
y
in
Cel
[2]
function
and
utations
the
,
progressiv
,
e
x
erasing
mo
in
mo
Kari
y
pro
k
of
=
The
Automaton
size
)
of
S
the
the
blo
ositiv
c
the
ks
(2
is
The
m
,
uc
follo
h
i
greater
c
than
i
the
d
neigh
cell
b
the
orho
most
o
erm
d
)
(6
;
r
size
;
d
6
and
r
v
;
and
:
b
:
wing
:
0
6
[
r

)
v
,
is
where
.
r
c
is
that
the
.
greater
of
of
the
the
:
radii
for
of
let
the
=
rev
=
ersible
T
ca
(
and
)
of
blo
its
a
in
dated
v
ens
erse
this
But
o
the
T
width
the
of
partition
the
e
blo
R
c
the
k
the
is
Rev
constan
c
t
and
6
8
r
2
.
8
W
x
e
k
giv
+
e
(
another
y
construction
x
with
y
only
x
d
k
+
div
1
(
bp
)
.
k
There
2.1
is
Cel
an
(
imp
is
ortan
(
t
r
dra
,
wbac
adius
k
strictly
to
natural
this
er
the
c
width
maps
of
+1)
the
S
blo
al
c
G
ks
conurations
is
es
3(
8
d
;
+
Z
1)
A
r
i
instead
c
of
[
6
]
r
:
.
of
Within
ends
this
states
construction
whic
the
distance
origins
.
of
k
the
A
bp
(
are
deed
translated
d
b
;
y
where
3
is
r
of
whereas
h
b
v
efore
is
they
mo
tak
i
e
Z
all

v
).
alues
blo
in
the
f
of
0
[
;
v
3

r
;
g
]
d

.
0
All
]
deitions
function
and
p
pro
S
ofs
all
in
the
this
are
article
sa
can
is
b
the
e
blo
read
erm
without
0
an
,
y
wing
previous
er
kno
an
wledge
C
of
y
the
d
sub
=
ject
and
The
mo
article
that
is
:
structured
,
as
(
follo
=
ws
j
The
+
deitions
.
of
ords
Cellular
k
Automata
i
(
partition
ca
is
),
to
Blo
same
c
all
k
ks
P
The
erm
of
utations
T
(
o
bp

)
It
and
as
rev
with
ersibilit
shifted
y
.
are
Blo
giv
utomaton
en
Blo
in
A
Section
osition
2.
bp
In
size
Section
.
3,
y
for
and
an
P
y
sync
rev
ely
ersible
that
ca
x
A
y
,
Z
w
,
e
k
exhibit
(
2
+
d
)
bp
=
suc
k
h
y
that
,
the
x
global
d
function
)
of
=
A
k
is
d
a
k
restriction
(
of
div
their
)
comp
=
osition
k
This
y
pro
and
v
x
es
y
the
k
conjecture
x
In
:y
Sect
.
4,
Cellular
w
A
e
lular
giv
utomaton
e
ca
a
A
construction
deed
with
y
only
d
d
;
+
;
1
)
bp
where
,
r
but
r
with
a
wider
p
blo
e
c
n
ks
b
2
and
Deitions
lo
Let
al
d
f
b
S
e
r
a
d
strictly
to
p
.
ositiv
glob
e
function
in
A
teger
A
Cellular
maps
automata
in
and
themselv
blo
as
c
ws
k
c
p
C
erm
8
utations
2
dee
d
mappings
G
o
(
v
)
er
=
d
(
-
j
dimensional
+[
inite
r
arra
r
ys
]
o
)
v
The
er
state
a
a
ite
dep
set
only
of
the
states
of
S
cells
.
h
W
at
e
at
denote
r
C
2.2
=
c
S
P
Z
utation
d
Blo
the
Permutation
set
bp
of
is
conurations
b
F
(
or
S
an
v
y
o
x
)
2
the
Z
v
d
an
,
t

Z
x
suc
is
that
the

shift
,
b
o
y
a
x
ordinate
:
dulo
8
(
c
,
2
2
C
d
;
0
8
o
i
v
2
The
Z
asic
d
ck
;
is

follo
x
subset
(
Z
c
:
)
[
i
;
=
1
c
]
i
[
+
0
x
v
.
]
The

set

of

in
[
tegers
;
f
d
i
]
i
The
+
e
1
a
;
erm
i
of
+
V
2
When
;
the
:
of
:
blo
:
k
j
equal
g
e
is
y
denoted
it
[
the
[
of
i
bp
j
The
]
c
]
p
.
utation
F
origin
or
,
an
0
y
is
conuration
follo
c
mapping
and
v
an
C
y
for
subset
y
E
2
of
,
Z
an
d
i
,
Z
c
,
j
a
E
i
is
v
the
b
restriction
i
of
d
c
so
to
i
E
a
.
v
W
b
e
then
denote
0
<
c
and
i

e
the
c
follo
a
wing
v
orders
V
o
b
v
In
er
w
Z
the
d
c
:
whic
x
holds
<
in
y
regular
,
issued
8
0
k
up
;
according
x
e
k
The
<
happ
y
to
k
the
and
c
x
of

partition
y
Blo
,
Permutation
8
origin
k
,
;
o
x

k


0
y

k
.
.
is
W
same
e
b
denote
but
+
the
,
is
mo
b
d
o
,
W
div
call
and
ck
:
A
the
or
p
eversible
oin
ck
t
lular
wise
utomaton
v
comp
ectorial
of
addition
arious
mo
with
dulo
same
Eulerian
and
division
e
and
2.3
m
ersibilit
ultiplicatio
Both
n
Automata
o
Blo
v
k
er
erm
Z
are
d
hronous
.
massiv
This
parallel
means
2A
Cellular
Automaton
A
1
the
:
is
u
r
:
eversible
b
if
next
and
v
only
lex
if
;
G
succ
A
d
is
not
bijectiv
v
e
is
and
W
there
st
is
;
another
1)
ca
:
B
greater
suc
b
h
rev
that
,
G
A
1
the
A
a
=
of
G
is
B
cellular
.
of
Suc
going
h
with
an
of
automaton
0
B
(0
is
;
called
:
the

in
:
v

erse
g
of
:
A
d
.
1
Rev
y
ersible

ca
b
are
b
denoted
a
ra
`v
.
second
Amoroso
f
and
automaton
P
is
att
c
[1
consider
]
that
giv
b
e
A
an
b
algorithm
that
whic
more
h
Notations
decides
;
whether
deed
a
n
1
then
imensional
or
cellular
:
automata
:
is
0
rev
:
ersible
:
or
1
not

Kari
:
[5

]
1
pro
(1
v
.
es
the
that
f
the
e
rev
;
ersibilit
it
y
0
of
for
ca
if
is
erm
undecidable
obtained
in
0
greater
dee
dimensions

By
(
construction
um
blo
The
c
bp
k
2
p
whic
erm
S
utations
comp
are
the
rev
its
ersible
r
One
b
simply
ersible
uses
e
the
that
in
pro
v
d
erse
p
p
W
erm
A
utation
wn
on
radius
the
enough
same
rev
partition
A
to
.
get
6
the
the
in
the
v
e
erse
need
blo
b
c
on
k
e
partition
f
2.4
g
Sim
order
ulation
follo
Since
y
ca
b
are
s
iterativ
kw
e
.
w
(0
e
:
use

the
;
follo
0)
wing
1
deition
:
F

or

an
;
y
0
t
(1
w
0
o
:
functions
;
f
;
:
:
F
:
!
;
F
0
and
1)
g
:
:
1
G
:
!
succ
G
b
,
elemen
g

simulates
;
f
.
if
>
there
;
exist
;
t
1))
w
es
o
to
enco
1
ding
is
functions
It

noted
:
s
F
are
!
exactly
G
order
and
or

2
:
1
G
w
!
shift
F
b
,
r
space
#
and
)
time
the
inexp
er
ensiv

e
of
compared
of
to
(
f
f
and
?
g
b
,
do
and
elong
a
and
function
The
'
t
:
state
N
and

onen
F
state
!
d
N
;
suc
)
h
e
that
rev
8
cellular
x
W
2
pro
F
e
;
it
8
the
n
duct
2
2
N
blo
,
k
f
erm
n
tations
(
e
x
that
)
1
=
kno

and

the
g
r
'
large
(
for
n
oth
)
ersible

automata

and
(
1
x
Let
)
=
.
r
This
e
corresp
width
onds
all
to
bp
the
w
comm
built
uting
e
diagram
some
of
deitions
Fig
efore
1.
further
The
3.1
function
W
g
use
can
set
b
0
e
1
used
d
instead
the
of

f
as
for
ws
iterating
b
8
the
n
um
2
er
N
1
;
and
0
bac

ard
n
icographically
F
F

example
G
;
g
;
'
:
(
0)
n
(1
)
0
f
:
n
:
F

;
G
;
?
;
6
:
-
0)
-
:
Figure
:
1:
(0
g
0
sim
:
ulates
:
f
;
.

Sim
;
ulation
;
is
;
a
:
transitiv
0)
e
(1
relation
0
A
1
sim
0
ulation
:
is
0)
in
:
line
:
ar
(0
time
:

:
if
;
'
;
(

n
:
:

)
;
=
;

:
n
1)
for
Let
all
(
natural
)
n
e
.
least
If
t
b
than
oth
in
f
0
and
1
g
d
are
W
in
denote
v
for
ertible
((1
and
1
g
1
sim
:
ulates
:
f
,
,
do
b
not
y
elongs
the
f
unicit
;
y
g
of
but
predecessors
practical
the
writing
function
should
'
e
can
that
b
0
e
and
extended
s
so
p
that
uted
the
the
equalit
erse
y
is
f
F
n
an
=

f

;
g
g
'
,
(
e
n
the
)
&

to

e
still
3
holds
:
for
and
n
1
negativ

e
to
An
e
automaton
n
sim
b
ulates
of
another
in
if
.
and
set
only
sym
if
ols
its
the
global
is
function
S
sim
[
ulates
)
the
where
global
is
function
sym
of
ol
the
h
other
es
3
b
Construction
to
of
A
the
means
Blo
oid
c
st
k
onen
P
is
artition
old
Represen
of
tation
cell
Let
the
A
comp
=
t
(
new
S
The
;
3sets
corresp
ond
to
states
Blo
,
where
;:::
the

old
i
states
[
are
of
deleted
)
and

the
F
new
i
states
(
are
0)
added
c
E
f
O
go

T
=
The
Y
pro
1
and

orking
i
states

r
d
r
[
O
[
d
(2+2
c

c
i
.
)
;
r
2
;
blo
(4+4
(