Laboratoire Bordelais de Recherche en Informatique

Jérôme 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 1157-97 Grain Sorting in the One-dimensional Sand Pile Model Jérôme Durand-Lose labri, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. Abstract We study the evolution of a one-dimensional pile, empty at rst, which receives a grain in its rst stack at each iteration. The nal position of grains is singular: grains are sorted according to their parity. They are sorted on trapezoidal areas alternating on both sides of a diagonal line of slope p 2. This is explained and proved by means of a local study. Each generated pile, encoded in height dierences, is the concatenation of four patterns: 22, 1313, 0202, and 11. The relative length of the rst two patterns and the last two patterns converges to p 2. We make asymptotic expansions and prove that all the lengths of the pile are increasing proportionally to the square root of the number of iterations. 1 Introduction We consider an innite sequence of stacks. Each stack can hold any nite number of grains, this number is called the height of the stack.

• model gradian-driven


• since grains


• trapezoidal areas


• grain


• dimensional lattice


• labeling grains


• grain model


• local interaction

Sujets

• Laboratoire bordelais de recherche en informatique
• University of Bordeaux

Informations

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

Extrait

w
La
of
b
on
oratoire
in
B
[6,
ordelais
aux
de
t
R
is
ec
elfrganized
herc
v
he
spm
en
c
I
the
nformatique
nets
ura
data
cnrs
whic
1
admits
304,
,
Univ
whatev
ersit
olution
Bordeaux
as
I
one
351,
and
cours
b
de
a
la
oneimensional
Lib
and
ation
in
33
gradianriv
405
cessor
T
ely
alence
v
Cedex
gran
France
lik
.

Rapp
and
ort
v
de
w
Rec
in
herc
at
he
h
Numo
hourglass
1157-97
that
Grain
cess
Sorting
i
in
k
the
h
Oneimensional
n
Sand
ab
Pile
[3
Mo
oth
del
they
Je
enco
Durandose
lik

used
l
o
a
used
bri
balancing
,
stac
ura
[12
cnrs
simple
1
lo
304,
all
Univ
same
ersit
imp
Bordeaux
in
I
ts
351,
v
cours
is
de
[2
la
sequen
Lib
g
ation
ha
F
of
405
of
T
ed
alence
cases
Cedex
is
France
spm
.
receiv
Abstract
stac
W
also
e
a
study
w
the
mo
ev
alen
olution
dee
of
bri
a
t
oneimensional
x
pile
a
empt
es
y
to
at
its
st
if
whic
b
h
hips
receiv
v
es
v
a
4].
grain
case
in
dels
its
automata
st
equiv
stac
some
k
Both
at
g
eac
P
h
],
iteration
mo
The
computing
al
of
p
spm
osition
mo
of
dynamic
grains
mo
is
tasks
singular
a
grains
w
are
The
sorted
d
according
and
to
ensiv
their
rearrangemen
parit
ensures
y
cessors
.
almost
They
t
are
spm
sorted
t
on
o
trap
ysics
ezoidal
v
areas
trop
alternating
functions
on
the
b
y
oth
to
sides
=f
of
9,
a
].
diagonal
oneimensional
line
related
of
studied
slop
8].
e
e
p
the
2
al
.
the
This
iterations
is
as
explained
dynamics
and
sequen
pro
problem
v
pap
ed
parallel
b
a
y
empt
means
whic
of
a
a
its
lo
at
cal
It
study
e
.
dripping
Eac
but
h
section
generated
dee
pile
cf
enco
and
ded
are
in
in
heigh
e
t
dripping
dirences

is
bor
the
,
concatenation
o
of
ord
four

patterns
1
22
stac
,
giv
1313
a
,
hip
0202
eac
,
of
and
neigh
11
ors
.
its
The
um
relativ
er
e
c
length
is
of
o
the
e
st
certain
t
alue
w
,
o
In
patterns
oneimensional
and
b
the
mo
last
are
t
cellular
w
and
o
are
patterns
alen
con
via
v
simple
erges
ding
to
spm
p
cf
2
,
.
e
W
etri
e
[11
mak
are
e
to
asymptotic
del
expansions
parallel
and
the
pro
ws
v
information
e
systems
that
is
all
to
the
del
lengths
en
of
load
the
Grains
pile
del
are
or
increasing
and
prop
ks
ortionall
pro
y
net
to
ork
the
].
square
aim
ro
to
ot
a
of
fast
the
relativ
n
inexp
um
e
b
cal
er
t
of
h
iterations
that
1
pro
In
ha
tro
e
duction
the
W
amoun
e
of
consider
ork
an
is
inite
ortan
sequence
for
of
ular
stac
ws
ks
ph
Eac
It
h
in
stac
arian
k
en
can
y
hold
e
an
and
y
eris
ite
soalled
n
criticalit
um
and
b
related
er
the
of
1
grains
phenomenon
this
,
n
10
um
13
b
The
er
tial
is
spm
called
the
the
cf
height
are
of
in
the
7,
stac
They
k
v
The
pro
Sand
ed
pile
uniqueness
mo
the
del
pile
(
er
spm
order
)
the
and
as
Chip
ell
ing
describ
games
the
(
in
cf
arious
g
tial
)
The
are
studied
based
this
on
er
lo
the
cal
ev
in
of
teractions
oneimensional
Both
,
mo
y
dels
st
conserv
h
e
es
the
grain
total
to
n
st
um
k
b
eac
er
iteration
of
can
grains
b
In
seen
spm
sand
,
in
a
thin
grain
long
go
In
es
2,
to
e
a
the
neigh
and
b
g
or
dels
stac
recall
k
they
if
equiv
the
t
heigh
dimension
t
W
dirence
also
b
the
et
pro
w
studied
een
jduranda
stac
.u-
ks
de
is
r
more
httpep
than
inf
a
abr
giv
-b
en
eau
threshold
r
whereas
jdur
in
.
cf
g2
In
e
section
the
3,
(
w
3
e
spm
pro
b
v
is
e
b
that
direct
the
e
generated
;
piles
getting
in

heigh
=
t
n
dirences
4
are
i
made
14
of
pile
four
ks
patterns
0
22
(
,
i
1313
stac
,
the
0202
een
and
)
11
i
.
+
The
of
fron
-
tiers
2
b
1
et
]]
w
7
een
e
patterns
mo
act
sequences
lik
N
e
an
signals
Deiti
The
2
silhouette

of
the
eac

h
i
pile
1
is
y
made
corresp
of
All
t
pro
w
of
o
'
parts

of
this
diren
(
t
i
slop
2
es
2
2
n
then
equal
1
-
.
-
In
h
section
b
4,
]]
grains
i
are
5
mark
3
ed
c
dep
1
ending
1
on
a
their
Since
parit
smaller
y
es
.
the
Ev
an
en
zero
and
b
o
o
dd
ys
grains
(
are
threshold
arranged
n
in
otherwise
a
pile
v
driv
ery
function
sp
=
ecial
2
w
F
a
(
y
+
they
)
are
to
lo
grain
cated
p
in
p
trap
the
ezoidal
are
areas
this
alternating
2
on
b
b
dirences
oth
an
sides
=
of
)
a

diagonal
i
line
transition
of
=
slop
)
e
+
p
(
2
(
.
x
W
+1
e
of
explain
t
this
b
b
is
y
the
lo
b
oking
-
lo
-
cally
6
at
]]
the
2
in
i
teractions
[[
b
1
et
h
w
0
een
d
mo
[[
ving
2
grains
h
and
1
signals
e
In
a
section
3
5,
h
w
1
e
i
giv
c
e
1:
asymptotic
17
appro
are
ximations
ed
of
ks
the
pro
diren
only
t
generated
parameters
pile
W
no
e
t
do
decreasing
this
ensures
b
t
y
w
making
t
a
e
con
alw
tin
ositiv
uous
1
appro
)
ximation
follo
of
8
the
,
pile
=1
and
n
use
.
a
e
diren
dynamics
tial
dripping
resolution
b
as
wing
in
:
[1
)
].
0
W

e
+
pro
<
v

e

that
i
the
2
length

o