//img.uscri.be/pth/866c5f18be20cdaf2322a710b04e84ecee0fa4df
La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Laboratoire Bordelais de Recherche en Informatique

De
10 pages
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


Voir plus Voir moins

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
(