Laboratoire Bordelais de Recherche en Informatique

Jérôme Olivier Durand - Lose

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

Sujets

• Laboratoire bordelais de recherche en informatique
• University of Bordeaux
• Cellular automaton
• Natural foods

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 11
• Langue: English

Extrait

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