Asymptotic behavior in a heap model with two pieces.
In a heap model, solid blocks, or pieces, pile up according to the Tetris game mechanism. An optimal schedule is an infinite sequence of pieces minimizing the asymptotic growth rate of the heap. In a heap model with two pieces, we prove that there always exists an optimal schedule which is balanced, either periodic or Sturmian. We also consider the model where the successive pieces are chosen at random, independently and with some given probabilities. We study the expected growth rate of the heap. For a model with two pieces, the rate is either computed explicitly or given as an infinite series. We show an application for a system of two processes sharing a resource, and we prove that a greedy schedule is not always optimal.
Introduction
Heap models have recently been studied as a pertinent model of discrete event
systems, see Gaubert & Mairesse [19,20] and Brilman & Vincent [12,13]. They
provide a good compromise between modeling power and tractability. As far
as modeling is concerned, heap models are naturally associated with trace
monoids, see [31]. It was proved in [20] that the behavior of a timed one-
bounded Petri net can be represented using a heap model (an example appears
in

Figure

1). We can also mention the use of heap models in the physics of
This work was partially supported by the European Community Framework IV
programme through the research network ALAPEDES ("The ALgebraic Approach
to Performance Evaluation of Discrete Event Systems")
Preprint submitted to Elsevier Preprint 26 October 2000
surface growth, see [5]. The tractability follows essentially from the existence
of a representation of the dynamic of a heap model by a (max,+) automaton,
see [13,19].
A heap model is formed by a finite set of slots R and a finite set of pieces
A. A piece is a solid block occupying a subset of the slots and having a poly-
omino shape. Given a ground whose shape is determined by a vector of R R
and a word we consider the heap obtained by piling up
the pieces a in this order, starting from the ground, and according to
the Tetris game mechanism. That is, pieces are subject to vertical translations
and occupy the lowest possible position above the ground and previously piled
pieces. Let y(w) be the height of the heap w. We define the optimal growth
rate as ae min = lim inf n minw2A n y(w)=n. An optimal schedule is an infinite word
such that lim n is the prefix of length n of
u. An optimal schedule exists under minimal conditions (Proposition 4). We
can define similarly the quantity ae max and the notion of worst schedule. The
problem of finding a worst schedule is completely solved, see [17,19]. Finding
an optimal schedule is more difficult, the reason being the non-compatibility
of the minimization with the (max; +) dynamic of the model. In [21], it is
proved that if the heights of the pieces are rational, then there exists a periodic
optimal schedule. If we remove the rationality assumption, the problem
becomes more complicated. Here we prove, and this is the main result of the
paper, that in a heap model with two pieces, there always exists an optimal
schedule which is balanced, either periodic or Sturmian. We characterize the
cases where the optimal is periodic and the ones where it is Sturmian. The
proof is constructive, providing an explicit optimal schedule.
As will be detailed below, a heap model can be represented using a specific
type of (max,+) automaton, called a heap automaton. A natural question is the
Given a general (max,+) automaton over a two letter alphabet, does
there always exist an optimal schedule which is balanced (for an automaton
defined by the triple (ff; -; fi), set define an optimal
schedule as above)? The answer to this question is no, which emphasizes the
specificity of heap automata among (max,+) automata. A counter-example is
provided in Figure 4.
We also consider random words obtained by choosing successive pieces inde-
pendently, with some given distribution. We denote by ae E the average growth
rate of the heap. Computing ae E is in general even more difficult than computing
ae min . In [21], ae E is explicitly computed if the heights of the pieces are
rational and if no two pieces occupy disjoint sets of slots. Here, for models with
two pieces, we obtain an explicit formula for ae E in all cases but one where ae E
is given as an infinite series.
To further motivate this work, we present a manufacturing model studied by
Gaujal & al [23,22]. There are two types of tasks to be performed on the same
a
a b
Fig. 1. One-bounded Petri net and the associated heap model.
machine used in mutual exclusion. Each task is cyclic and a cycle is constituted
by two successive activities: one that requires the machine (durations: ff 1 and
and one that does not (durations: ff 2 and fi 2 respectively).
Think for instance of the two activities as being the processing and the packing.
This jobshop can be represented by the timed one-bounded Petri net of Figure
1. The durations ff are the holding times of the places. As
detailed in [20], an equivalent description is possible using the heap model
represented in Figure 1. The height of a heap a 1 corresponds
to the total execution time of the sequence of tasks a executed in this
order. An infinite schedule is optimal if it minimizes the average height of the
heap, or equivalently if it maximizes the throughput of the Petri net. We do
not make any restriction on the schedules we consider. In particular we do not
impose a frequency for tasks a and b. As a justification, imagine for instance
that the two tasks correspond to two different ways of processing the same
object. We prove in x7.4 that if ff
then there is a Sturmian optimal schedule; otherwise there exists a balanced
periodic optimal schedule. We also show in x7.5 that the greedy schedule is
not always optimal.
Assume now that in the model of Figure 1, the successive tasks to be executed
are chosen at random, independently, and with some probabilities p(a) and
p(b). If ff 1 or fi 1 is strictly positive, then we obtain an exact formula for ae E .
It enables in particular to maximize the throughput over all possible choices
for p(a) and p(b), see x8 for an example.
Let us compare the results of this paper with other cases where optimality
is attained via balance. In Hajek [25], there is a flow of arriving customers
to be dispatched between two queues and the problem is to find the optimal
behavior under a ratio constraint for the routings. The author introduces the
notion of multimodularity, a discrete version of convexity, and proves that a
multimodular objective function is minimized by balanced schedules. Variants
and extensions to other open queueing or Petri net models have been carried
out in [1,2], still using multimodularity. In a heap model however, one can
prove that the heights are not multimodular. In [22,23], the authors consider
the model of Figure 1. They study the optimal behavior and the optimal
behavior under a frequency constraint for the letters. Balanced schedules are
shown to be optimal and the proofs are based on various properties of these
sequences. We consider a more general model. For the unconstrained problem,
we prove in Theorem 14 that balanced schedules are again optimal. On the
other hand, under frequency constraints, we show in x7.6 that optimality is not
attained via balanced words anymore. Our methods of proof are completely
different from the ones mentioned above.
The paper is organized as follows. In x2 and x3, we define precisely the model
and the problems considered. We prove the existence of optimal schedules under
some mild conditions in x3.1. In x4, we recall some properties of balanced
words. We introduce in x5 the notions of completion of contours and completion
of pieces in a heap model. We prove in x6 that it is always possible to
study a heap model with two pieces by considering an associated model with
at most 3 slots. We provide an enumeration of all the possible simplified mod-
els: there are 4 cases. In x7.1-7.4, we prove the result on optimal schedules,
recalled above, by considering the four cases one by one. Greedy scheduling
is discussed in x7.5, and ratio constraints in x7.6. In x8, we study the average
growth rate.
Consider a finite set R of slots and a finite set A of pieces. A piece a 2 A is a
rigid (possibly non-connected) "block" occupying a subset R(a) of the slots.
It has a lower contour and an upper contour which are represented by two row
vectors l(a) and u(a) in (R[f\Gamma1g) R with the convention l(a)
if r 62 R(a). They satisfy u(a) - l(a). We assume that each piece occupies at
least one slot, 8a 2 A;R(a) 6= ;, and that each slot is occupied by at least
one piece, 8r 2 R;9a 2 A; r 2 R(a). The shape of the ground is given by a
vector I 2 R R . The 6-tuple constitutes a heap model.
The mechanism of the building of heaps was described in the introduction. It
is best understood visually and on an example.
Example 1 We consider the following heap model.
are strictly positive reals. We have represented, in
Fig. 2, the heap associated with the word
I
a
a
a
a
a
a
Fig. 2. Heap associated with the word ababa.
We recall some standard definitions and notations. We denote by 1fAg the
function which takes value 1 if A is true and 0 if A is false. We denote by R+
the set of non-negative reals, and by N   and R   the sets Nnf0g and Rnf0g.
Let A be a finite set (alphabet). We denote by A   the free monoid on A, that
is, the set of (finite) words equipped with concatenation. The empty word is
denoted by e. The length of a word w is denoted by jwj and we write jwj a for
the number of occurrences of the letter a in w. We denote by alph(w) the set
of distinct letters appearing in w. An infinite word (or sequence) is a mapping
A. The set of infinite words is denoted by A ! . An infinite word
there exists l 2 N   such that u In
this case, we write We denote by the prefix
of length n of u.
When A is the set of pieces of a heap model, (infinite) words will also be
called schedules. We also interpret a word w 2 A   as a heap, i.e. as
a sequence of pieces piled up in the order given by the word.
The upper contour of the heap w is a row vector xH (w) in R R , where xH (w) r
is the height of the heap on slot r. By convention, xH I, the shape of the
ground. The height of the heap w is
We recall that a set K equipped with two operations \Phi
and\Omega is a semiring
if \Phi is associative and
commutative,\Omega is associative and distributive with
respect to \Phi, there is a zero element 0 (a \Phi
unit element 1
The set is a semiring, called the (max,+) semir-
ing. From now on, we use the semiring notations:
semiring Rmin is obtained from Rmax by replacing max by min
and \Gamma1 by +1. The subsemiring
\Phi;\Omega ) is the Boolean semiring.
We use the matrix and vector operations induced by the semiring structure.
For matrices A; B of appropriate sizes,
We usually omit
the\Omega sign, writing for instance AB instead
of
A\Omega B. On the other hand, the operations denoted by +; \Gamma; \Theta and = always
have to be interpreted in the conventional algebra. We define the 'pseudo-
norm' jAj We denote by 0, resp. 1, the vector or matrix whose
elements are all equal to 0, resp. 1 (with the dimension depending on the
context).
For matrices A and B of appropriate sizes, the proof of the following inequality
is immediate:
\Phi\Omega
For matrices U; V and A of appropriate sizes and such that all the entries
of U; V; UA and V A are different from 0, the following non-expansiveness
inequality holds:
Given an alphabet A, a (max,+) automaton of dimension k is a triple
are the initial and final vectors
and
max is a monoid morphism. The morphism -
is entirely defined by the matrices -(a); a 2 A; and for
we have (product of matrices in Rmax ). The map
is said to be recognized by the (max,+) au-
tomaton. A (max,+) automaton is a specialization to Rmax of the classical
notion of an automaton with multiplicities, see [8,16].
An automaton (ff; -; fi) of dimension k over the alphabet A is represented
graphically by a labelled digraph. The graph has k nodes; if
there is an arc between nodes i and j with labels a and -(a) ij
there is an ingoing arrow at node i with label ff i and if fi j ? 0 then there is
an outgoing arrow at node j with label fi j . Examples appear in Figures 9,10
or 11.
For each piece a of a heap model H, we define the matrix M(a) 2 R R
by
Example 2 In the model considered in Figure 1 and Example 1, the matrices
associated with the pieces are
The entries have to be interpreted in Rmax .
Variants of Theorem 3 are proved in [13,19,20].
Theorem 3 Let I) be a heap model. For a word
, the upper contour and the height of the heap satisfy (products in
More formally, yH is recognized by the (max,+) automaton (I; M;1).
From now on, we identify the heap model and the associated (max,+) au-
tomaton, writing either We also call
H a heap automaton.
3 Asymptotic Behavior
Consider a (max,+) automaton its recognized map y. We
define the optimal growth rate (in R[ f\Gamma1g) as:
ae min
min
An optimal schedule is a word w 2 A ! such that lim n
We define the worst growth rate as ae max
A worst schedule is defined accordingly.
Consider a probability law fp(a); a 2 Ag (p(a) 2 [0; 1];
Random words are built by choosing the successive letters independently and
according to this law. Let p(w); n; be the probability for a random
word of length n to be w. We have
. When it exists, we define the average growth rate as:
p(w) \Theta y(w) : (7)
The optimal problem consists in evaluating ae min (U) and finding an optimal
schedule. The worst case problem consists in evaluating ae max (U) and finding
a worst schedule. The average case problem consists in evaluating ae E (U ).
When we consider a heap automaton H, the limits ae min (H); ae max (H) and
ae E (H) correspond respectively to the minimal, maximal and average asymptotic
growth rate of a heap.
3.1 Preliminary results
We consider the optimal problem first. It follows from (2) that
As a consequence
of the subadditive theorem, we have
lim nn
min
jwj=n
min
jwj=n
We also have for all w 2 A   ,
\Phi\Omega min
ff
i\Omega min
\Phi\Omega jffj
\Phi\Omega
When we deduce that ae min ae and that the lim inf is a
limit in (6).
Proposition 4 Let U = (ff; -; fi) be a (max,+) automaton such that 8i; ff i ?
and such that ae min (U) 6= 0. Then there exists an optimal schedule.
PROOF. It follows from (9) that the automata (ff; -; fi) and (1; -; 1) have
the same optimal schedules (if any). Since ae min 6= 0, we deduce from (8) that
for all k 2 N   , there exists w(k) 2 A   n feg such that
jw(k)j \Theta ae min - j-(w(k))j \Phi - jw(k)j \Theta (ae min
By the subadditive inequality (2), we then have, for all l 2 N   ,
Now define ~
and consider the infinite word ~
~
obtained by concatenation of the words ~
w(k). We consider
the prefix of length n of ~
w for an arbitrary n 2 N   . There exists k n 2 N
such that
~
where u is a prefix of w(k n 1). Using
(2) and (10), we get
ae min - j-( ~
kn
w(i))j \Phi
kn
w(i)j
ni
Obviously, k n is an increasing function of n and lim n!+1 k
we obtain that:
kn
w(i)j
ni
Let us take care of the last term on the right-hand side of (11). Note that
It implies that
a2A j-(a)j \Phi
a2A j-(a)j \Phi
Starting from (11) and using (12) and (13), we obtain that
It completes the proof.
We now consider the worst case problem. As above, if 8i; ff i ? 0;
the lim sup is a limit in the definition of ae max . As opposed to the optimal case,
the worst case problem is completely solved. We recall the main result; it is
taken from [17] and it follows from the (max,+) spectral theorem (the most
famous and often rediscovered result in the (max,+) semiring, see [15,4,28]
and the references therein).
Proposition 5 Let U = (ff; -; fi) be a trim (see x3.2) (max,+) automaton of
dimension k. Then, ae max (U) is equal to ae max (M), the maximal eigenvalue of
the matrix
a2A -(a). That is
ae
l
a ij be such that -(a ij be such that
say that
weight circuit of M). Then (a
worst schedule.
In the case of a heap automaton, there exists a worst schedule of the form u
where the period u is such that 8a 2 A; juj a - 1. For a heap automaton with
two pieces (a and b), a worst schedule can always be found among a ! , b ! and
example where the worst schedule is indeed (ab) ! appears in Figure
18.
3.2 Deterministic automaton
A (max,+) automaton (ff; -; fi) is trim if for each state i; there exist words u
and v such that ff-(u) i ? 0 and -(v)fi i ? 0. It is deterministic if there exists
exactly one i such that ff i ? 0; and if for all letter a and for all i, there exists
at most one j such that -(a) ij ? 0. It is complete if for all letter a and for all
there exists at least one j such that -(a) ij ? 0.
A heap automaton is deterministic if and only if there is a single slot. On the
other hand, a heap automaton is obviously always trim and complete. In the
course of the paper, we consider other types of (max,+) automata: Cayley and
contour-completed automata. These automata will be deterministic, trim and
complete.
be a deterministic and trim (max,+) automaton over the
alphabet A. Let U 0 be the (min,+) automaton defined by the same triple (with
be the maps recognized by U and U 0 respectively.
Since U is deterministic, it follows that y U
\Gamma1. Defining the (min,+) matrix
and applying the (min,+) version of Proposition 5 (replace max by min everywhere
in the statement of the Proposition), we get that
ae min
the minimal eigenvalue of N . Also if (i
circuit, then (a
is an optimal schedule.
Proposition 6 Let U = (ff; -; fi) be a deterministic, complete and trim
(max,+) automaton over the alphabet A. Assume that
a2A -(a) is
an irreducible matrix (i.e. 8i;
We define the (R+ ; +; \Theta) matrix
a2A p(a) \Theta 1f-(a) ij ? 0g. Let - be the unique vector
satisfying - \Theta
1. The expected growth rate is
(the products are the usual
ones).
Proposition 6 is proved in [17]. It follows from standard results in Markov
chain theory (P is the transition matrix and - is the stationary distribution).
A consequence of Proposition 6 is that ae E (U) can be written formally as a
rational fraction of the probabilities of the letters. That is ae
R and S are real polynomials over the commuting indeterminates p(a); a 2 A.
More generally, it is possible, under the assumptions of Prop. 6, to obtain the
formal power series
as a rational fraction
(over the indeterminates x; p(a); a 2 A), see for instance [8].
Finitely distant automata. Two (max,+) automata
defined over the same alphabet A are said to be finitely distant if
Two heap automata (I; M;1) and are finitely distant. Indeed, according
to (3), we have
The asymptotic problems are equivalent for two finitely distant automata U
and V. That is ae schedules
coincide.
Since most heap automata are not deterministic, we can not apply the results
in (14) and Proposition 6 directly to them. We often use the following pro-
cedure: Given a (max,+) automaton, find a deterministic, trim, and finitely
distant automaton, then apply the above results to the new automaton.
Balanced Words
Balanced and Sturmian words appear under various names and in various areas
like number theory and continued fractions [29], physics and quasi-crystals [24]
or discrete event systems [25,22]. For reference papers on the subject, see [7,9].
A finite word u is a factor of a (finite or infinite) word
is a finite subsequence of consecutive letters in w, i.e.
for some i and n. A (finite or infinite) word w is balanced if j juj a \Gamma jvj a
for all letter a and for all factors u; v of w such that jvj. The balanced
words are the ones in which the letters are the most regularly distributed. The
shortest non-balanced word is aabb.
An infinite word u is ultimately periodic if there exist n 2 N   and l 2 N   such
that Sturmian word is an infinite word over a two
letters alphabet which is balanced and not ultimately periodic.
We now define jump words. Let us consider ff
We label the points fnff 1 by a, and the points fnff 2 by b.
Let us consider the set fnff 1 in its natural order
and the corresponding sequence of labels. Each time there is a double point,
we choose to read a before b. We obtain the jump word with characteristics
words are balanced. If ff 1 =ff 2 is rational then w is periodic;
if ff 1 =ff 2 is irrational then w is Sturmian.
a
a
a
a a
Fig. 3. Representation of the jump word (ff
It is also possible to define words as above except that we read b before a
whenever there is a double point. These words are still balanced and we still
call them jump words (below, when necessary, we will precise what is the
convention used for double points).
A more common but similar description of jump words uses cutting sequences.
There exists an explicit arithmetic formula to compute the n-th letter in a
given jump word (using the so-called mechanical characterization, see [9]).
Optimal schedules and balanced words. We prove in Theorem 14 that in
a heap model with two pieces, there always exist an optimal schedule which
is balanced. If we still consider a two letter alphabet but a general (max,+)
automaton, then this is not true anymore. The counter-example below was
suggested to us by Thierry Bousch [10]. Consider the deterministic (max,+)
automaton (ffi; -; 1) represented in Figure 4. It is easy to check that ae
and that an optimal schedule is the non-balanced word (aabb) ! . No balanced
word is optimal in this example.
1Fig. 4. (Max,+) automaton with no balanced optimal schedules.
5 Completion of Profiles and Pieces
5.1 Cayley automaton
Given A in R k\Thetal
, we define -(A) in R k\Thetal
and
that -(A) is the normalized matrix associated with A.
Let us consider a (max,+) automaton over the alphabet A. We
define
In the case of a heap automaton H, -(H) is the set of normalized upper
contours.
Assume that -(U) is finite. Then we define the Cayley automaton of U as
follows. It is the deterministic (max,+) automaton (ffi; -; fl) of dimension -(U)
over the alphabet A, where for
and fl It follows from this definition that for w 2 A   , -(w)
Hence we have
We just proved that the automaton U and its Cayley automaton recognize the
same map (see also [17]).
The dimension of the Cayley automaton is in general much larger than the
one of U . However, it is deterministic, complete, and assuming for instance
that 8i; fi i ? 0, it is also trim. In particular when H is a heap automaton and
-(H) is finite, then the Cayley automaton is deterministic, complete and trim.
The Cayley automaton is used in x7.2.
The procedure described above is similar to the classical determinization algorithm
for Boolean automata. The difference is of course that -(U) is always
finite in the Boolean case.
5.2 Contour-completed automaton
Given a heap model H, it is easy to see that -(H) is infinite as soon as there
exist two pieces a and b whose slots are not the same. This motivated the
introduction in [21] of the refined notion of normalized completed contours. In
some cases, the set of such contours will be finite whereas -(H) is infinite. Here,
we recall only the results that will be needed. For details, and in particular
for an algebraic definition of completion in terms of residuation, see [21].
Let us consider a heap model described as the
We associate with the piece a 2 A, the upper
contour piece a and the lower contour piece a defined as follows
We still denote by M(a);M(a), the matrices defined as in (4) and associated
with the new pieces a; a.
An example of upper and lower contour pieces is provided in Figure 5. For
clarity, pieces of height 0 are represented by a thick line.
piece a
piece a
piece a
Fig. 5. A piece and the associated upper and lower contour pieces.
Given a vector x 2 R R
interpreted as the upper contour of a heap, we define
the completed contour OE(x) 2 R R
as follows
aji2R(a)
The vector OE(x) can be loosely described as the maximal upper contour such
that the height of a heap piled up on x is the same as the height of a heap
piled up on OE(x). More precisely, we have
For the sake of completeness, let us prove (19). Given a word
we define
We are going to prove the following results which put together imply (19)
It follows from the definition that (21) and (22) hold for the empty word e
(setting Assume now that (21) and (22) hold for all words of length
less or equal than n. We consider the word wa where w is of length n and a
is a letter.
If i 62 R(a) and i 62 R(w), then
Since obviously OE(x)M(w)M(a) i - xM(w)M(a) i , we get that
This concludes the proof of (21)
and (22), hence of (19).
Given a contour x 2 R R
, we define the normalized completed contour
-(OE(x)). Let us define
Let us assume that '(H) is finite. Then we define the contour-completed automaton
of H. It is a deterministic, complete and trim (max,+) automaton
over the alphabet A, of dimension '(H). It is defined by (ffi; -; 1) where for
The automaton H and its contour-completed automaton recognize the same
map, i.e.
The proof is analogous to the one of (17). The contour-completed automaton
is used several times in x7, see for instance Example 16.
5.3 Piece-completed heap automaton
After having defined the completion of contours, we introduce in this section
the completion of pieces.
We define the upper-completed pieces a ffi ; a 2 A, and the lower-completed pieces
a
min
We check easily that u(a hence we have indeed
defined pieces. Let us comment on this definition. Let x be a piece such that
a 0 be the piece obtained by piling up a and the part
of the lower contour piece x corresponding to the slots R(x) " R(a). The
piece a 0 is such that the heaps a 0 x and ax are identical. Hence, the piece a ffi
can be interpreted as the piece with lower contour l(a) and with the largest
possible upper contour such that the asymptotic behavior of a heap is not
modified when replacing the occurrences of a by a ffi . There is an analogous
interpretation for the pieces a ffi . An illustration of upper and lower completion
is given in Example 8 and Figure 6.
With the heap automaton we associate the heap automaton
and the heap automaton H
Lemma 7 A heap automaton H is finitely distant from both the heap automaton
H ffi and the heap automaton H ffi .
PROOF. Let us set
a2A
a2A
We want to prove the following inequalities, for all w 2 A   ,
Since we have the left-hand side
inequalities in (26) and (27) follow immediately. Let us prove the right-hand
side inequality in (26), the proof of the one in (27) being similar.
First of all, for two words x and y over the alphabet A, we have (where R(x)
and R(y) are defined as in (20))
To prove (28), it is enough to remark that it follows from the definition in (4)
We need another intermediary result: for any two pieces a; b 2 A, we have
l
Furthermore, it is immediate that M(a This concludes the
proof of (29).
Obviously, the right inequality in (26) holds for words of length 1. Let us
assume that it holds for all words of length n. Let be a word of
length n+ 1. Assume there exists ng such that R(w i
then using (28), we get
with an analogous equality for M ffi . Setting
we deduce that we have
where the last inequality is obtained by applying the recurrence assumption to
the words u and v which are of length n. Assume now that R(w i )"R(w
for all be such that IM ffi . Assume that
The case remains to be treated. We obtain, using recursively
(29), that
We conclude that
by definition of K ffi . This completes the proof.
We define the bi-completed pieces a ffi
Here the pieces a ffi
are obtained by lower-completion first and then
upper-completion. We can also define pieces, say - a ffi
performing
upper-completion first and then lower-completion, that is: R(-a ffi
u(-a
min
In general, the pieces a ffi
are different, in other words the operations of
upper and lower-completion do not commute. An example of bi-completion is
provided in Figure 6. On this example, the pieces a ffi
are different.
Example 8 Consider the heap automaton with pieces defined by
It is simpler to obtain the completed pieces graphically, using the intuition
described above. We have represented in Figure 6 the upper, lower and bi-
completed pieces: fa
g.
The heap automaton H ffi
over the alphabet A, defined by
called the piece-completed heap automaton associated
with
Lemma 9 A heap automaton H and the associated piece-completed automaton
are finitely distant.
PROOF. By definition, we have H ffi
we get the result.
-a
a
a
a
a
Fig. 6. Two pieces and the associated upper-completed, lower-completed and
bi-completed pieces.
Given a set of pieces A, let us denote by A
ffi the upper-completed,
lower-completed and bi-completed sets of pieces. Given two pieces a and b, we
say that r is a contact slot for ab if
R(b) (visually, a is in contact with b at slot r in the heap ab).
We have
. In words,
a set of lower-completed (resp. upper-completed or bi-completed) pieces is left
unchanged by performing another lower (resp upper or bi) completion.
PROOF. The arguments below are based on the following immediate remark:
Given a and b in the same set of pieces, if i is a contact slot of ab then
By definition we have, 8a
It implies that j(i) is a contact slot for ba and that both i and j(i) are contact
slots for ba ffi . Obviously, it implies that i is a contact slot for b ffi a ffi and we
conclude that l((a This completes the proof of . The
proof of
Since i is a contact slot for b ffi a ffi , we also obtain that u(b ffi
for all k, we have M(b ffi
We also have that i is a contact slot for
. Using this together with (29), we get that 8k 2 R(b); 8l 2 R(a),
It implies that l((a ffi
We deduce that we have (a ffi
and we
can prove in a similar way that (a ffi
. We conclude that
Both the contour completion of x5.2 and the above piece completion are based
on the idea of local transformations which do not modify the asymptotic behavior
of heaps. However, they are different: the completed contours are not
the upper contours of the heaps of completed pieces.
6 Minimal Realization
The goal of this section is to prove that given a heap automaton with two
pieces, there exists a finitely distant one of dimension at most 3, Theorem 12.
A set of bi-complete pieces is a set A such that A ffi
A. From now on, we
always implicitly consider bi-complete pieces. Due to Lemma 9 and 10, we can
make this assumption without loss of generality.
be a heap automaton with set of slots R and let ~
R be a
subset of R. The heap model obtained by restriction of H to ~
R is denoted by
R and defined by H j ~
R\Theta ~
(visually, the new pieces are the
old ones restricted to ~
R).
Lemma 11 Let H be a heap automaton on the alphabet A and with set of
slots R. Let ~
R be a subset of R. The automaton H j ~
R is finitely distant from
H if and only if ~
R contains a contact slot for each word ab; a; b 2 A; such that
PROOF. Let Assume that ~
R contains at least one contact
slot for each ab such that R(a) " R(b) 6= ;. Let (a; b) be such a couple. We
have, by definition of a contact slot,
R\Theta ~
R\Theta ~
R\Theta ~
R\Theta ~
Let us consider a word w 2 A   . Using repeatedly the equality in (28), we
obtain that
belongs to I(w) if v is a subword
of w and if two consecutive letters of v, say v are such that R(v i
For each word v 2 I(w), we obtain by using repeatedly (30)
that M(v) j ~
R\Theta ~
R\Theta ~
R (v). We deduce that M(w) j ~
R\Theta ~
R\Theta ~
R (w). We
conclude easily that
1- sup
w2A
R\Theta ~
R (w)1
w2A
a2A
Hence, H j ~
R is finitely distant from H. We have shown that the condition is
sufficient. Let us prove that it is necessary. Assume that ab; R(a) " R(b) 6= ;,
has no contact slot in ~
R. Let ffi be the minimal gap between a and b in the
heap ab over the slots ~
R. Then we have jM(ab)j
R\Theta ~
R (ab)j
It implies that jM((ab) n )j
R\Theta ~
R ((ab) n )j \Phi - n \Theta ffi, showing that H and
R are not finitely distant.
Theorem 12 Let be a heap automaton with two pieces. Over
the same alphabet, there exists a heap automaton ~
M;1) of dimension
at most 3 and which is finitely distant from H.
PROOF. By choosing one contact slot for each one of the words aa; ab; ba and
bb, we obtain a set ~
R of cardinality at most 4 and such that the automaton
R is finitely distant from H, see Lemma 11. We now prove that 3 slots
are always enough. We define the application c
denotes the set of subsets of A 2 . The set c(r) contains xy if r is a contact
slot of xy. Assume that R(a) " R(b) 6= ; and consider a slot r 2 R(a) " R(b).
Let us prove that c(r) must contain words starting with a and b and words
finishing with a and b. Assume for instance that c(r) does not contain any
word starting with a. Then, according to (24), there exists x 2 A such that
Since ax does not belong to c(r), the maximum above is attained for j 6= r and
we have u(a This contradicts the fact that A is a set of bi-complete
pieces.
To summarize, we must have
If we have faa; bbg ae c(r) (resp. fab; bag ae c(r)), we complete the slot r with
a contact slot for the heap ab and one for the heap ba (resp. for aa and bb).
We have a set of at most 3 slots which satisfies the required properties.
Now assume that R(a) " It is enough for ~
R to contain a contact slot
of aa and one of bb, hence to be of cardinality 2, for H j ~
R to be finitely distant
from H. This completes the proof.
Performed on the original heap automaton, instead of the piece-completed
one, the above argument would not work. Consider the heap model H of
dimension 4 defined by
and There exists no proper subset ~
R of R such that H j ~
R is
finitely distant from H.
Example 13 Let us illustrate Theorem 12. We consider the heap automaton
of dimension 4 and consisting of the two bi-complete pieces
defined by
We have fbbg. Here,
we can choose either ~
or f1; 3; 4g and the heap automaton H j ~
R
will be finitely distant from H. This can be 'checked' on Figure 7. In this
a
a
Fig. 7. A heap automaton of dimension 4 and a finitely distant one of dimension 3.
example, we do not always have
R\Theta ~
R (w)1. However we can
check that 1 -
R\Theta ~
R (w)1 - 1.
Lemma 11 and Theorem 12 are minimal realization type of results. Here is
the generic problem of this kind: Given an automaton with multiplicities in a
semiring, find another automaton recognizing the same map and of minimal
dimension.
In a commutative field, the minimal realization problem is solved, see [8] for a
proof and references. In Rmax , it is a well-known difficult and unsolved problem,
see [18] for partial results and references. Here, our result is specific in several
ways. First, we look at a particular type of (max,+) automata, heap automata
with two pieces. Second, we look for a realization by a heap automaton and not
by an arbitrary (max,+) automaton. Third, we only require an approximate
type of realization, see (15).
6.1 Classification of heap models with two pieces
As a by-product of Theorem 12, to study heap automata with two pieces, it
is enough to consider automata with bi-complete pieces and of dimension at
most 3. We are going to show that there are only four cases which need to be
treated (up to a renaming of pieces and slots) which are:
We recall that the function c(:) was defined in the proof of Theorem 12.
(i) If R(a) " we have seen in the proof of Theorem 12, that the heap
model can be represented with two slots only, one for each piece.
(ii) Let us assume that r be such that aa 2 c(r). Using
(31), we have either faa; bbg ae c(r) or faa; ab; bag ae c(r). If we are in the
second case, we complete r with a contact slot for bb. If we are in the first
case, let us consider a slot r 0 such that ab 2 c(r 0 ). We have, as before, either
select the
slots g. If fab; aa; bbg ae c(r 0 ), then we complete r 0 with a contact slot for
ba. In all cases, we obtain a finitely distant heap model with at most two slots.
(iii) Let us assume that R(b) ae R(a); R(b) 6= R(a). Let r be a slot such that
must have either fbb; ab; bag ae c(r) or
c(r). In the second case, we conclude as in (ii). In the first case, we
complete r with a slot r 0 such that aa 2 c(r 0 ). Compared with (ii), there is a
new possible situation: two slots
(iv) Let us assume that R(a) " R(b) 6= ;; R(a)nR(b) 6= ;; R(b)nR(a) 6= ;.
We consider a slot r 2 R(a) " R(b) and such that ab 2 c(r). We have either
fab; aa; bbg ae c(r) or fab; bag ae c(r). In the first case, we complete r with a
slot r 0 such that ba 2 c(r 0 ). In the second case, we complete r with a contact
slot r a for aa and a contact slot r b for bb. Compared with the cases (ii) and
(iii), there is a new possible situation: three slots fr; r a ; r b g with
and g.
7 Heap Models with Two Pieces: Optimal Case
Let H be a heap model with two pieces. To solve the optimal problem, it is
sufficient to consider the typical cases described in x6.1. Two situations need
to be distinguished:
ffl H is 'determinizable', i.e. there exists a finitely distant, trim, and deterministic
ffl H is 'not-determinizable'.
For 'determinizable' automata, there exists a periodic optimal schedule. We
will see below that there are two cases where H is 'not-determinizable'. In both
cases, we are able to identify 'visually' the optimal schedules. The resulting
theorem can be stated as follows.
Theorem 14 Let us consider a heap model with two pieces. There exists an
optimal schedule which is balanced, either periodic or Sturmian.
PROOF. We consider in x7.1-7.4 the four different cases described in x6.1.
For each case, we prove that the results of Theorem 14 hold. Furthermore we
provide an explicit way to compute ae min (H) and an optimal schedule in each
case.
In the sections below, we always denote the heap model considered by
3g. Viewed as a
heap automaton, it is denoted by We always implicitly assume
that we are working with bi-complete pieces. We recall that by modifying the
ground shape in a heap automaton, we obtain a finitely distant automaton.
Below we choose the ground shape which is the most adapted to each case.
If one of the two pieces, say a, then the optimal problem
becomes trivial. We have ae min optimal schedule is
provided by a ! . From now on, we assume that l(a) 6= u(a) and l(b) 6= u(b).
We set
i2R(a)
7.1 The case
We assume that the ground shape is 1. We claim that the jump word u with
characteristics (see x4) is optimal. Furthermore, we have ae min
h a h b =(h a An example is provided in Figure 8.
We now prove these assertions. Let us pile up the pieces according
to the jump word u defined by (h a ; h b ; 0). We have, by construction,
Hence we have lim n xH (u[n]) 1
as the heap is without any gap, it implies immediately
that u is optimal. The optimal schedule u is balanced, periodic when h a =h b is
rational and Sturmian when h a =h b is irrational, see x4. We have
a
a
a
a
a
a
Fig. 8. The jump word (h a
ae min
h a ju[n]j a
To be complete, let us prove that it is not possible to find a periodic optimal
schedule in the case h a =h b irrational. Let v be a finite word and let us consider
the schedule v ! . Since h a =h b is irrational, we have h a jvj a 6= h b jvj b . Let us
assume that h a jvj a ? h b jvj b . It implies that jvj a ? jvjh b =(h a
h a jv n j a =jv n
7.2 The case
As
-(yM(b)), for all x; y 2 R 2 . Let us choose the ground shape to be -(1M(a)).
We have -(IM(b))g. Hence we can solve the optimal
problem using the Cayley automaton, see x5.1. Applying the results of x3.2, it
is always the case that one of the schedules a is optimal. These
schedules are obviously balanced.
Example 15 Consider the heap automaton H with pieces defined by
We have represented the pieces in Fig. 9. We check easily that
(the ground shape being (1; \Gamma1)). Let (ff; -; 1) be the Cayley
automaton and let We have
The minimal eigenvalue of the Rmin matrix M is 2, the circuits of minimal
a
a
a
Fig. 9. Heap model with two pieces and its Cayley automaton.
mean weight are f2g and f3g and M 22 = -(a) 22 ; M We have
ae min are optimal schedules.
7.3 The case
This case could be reduced to the case
one in x7.4) by adding a third slot and setting
We treat the case separately
in order to get more precise results. Let us set . For
Hence, we have
Assume that ffi - 0 and let the ground shape be equal to 1M(a). We have,
We deduce that
We also have 1M(ab n+1 By assumption, we have h b ? 0.
Hence there exists a smallest integer m such that
It implies, using (32), that 8n - m;'(1M(ab n We conclude that
We have proved that '(H) is finite. In the case ffi - 0, a similar analysis holds.
In all cases we can solve the optimal problem using the contour-completed
automaton and the results of x3.2. We have represented in Figure 10, the
a
a
a
a
a
Fig. 10. Contour-completed automaton
contour-completed automaton in the case m - 3 and (without the mul-
tiplicities). There are exactly m simple circuits in this automaton with
respective labels b and ab 2, the multiplicity
to go from '(1M(ab n )) to '(1M(ab n+1 )) is 1 while the one to go from
'(1M(ab n+1 )) to '(1M(a)) is always equal to h a . Hence the circuits of label
ab are not of minimal mean weight. We conclude that an
optimal schedule can be found among the schedules (ab m
is optimal). These schedules are balanced.
Example We consider the heap automaton with pieces a and b defined by
The pieces are represented in Figure 11. The completion operation has the
ab
a
a
a
Fig. 11. Heap model and its contour-completed automaton.
following
n. Hence we have \Gamma3)g. Let (ff; -; 1) be
the contour-completed automaton and let -(b)). The minimal
eigenvalue of M is ae min and the circuit of minimal mean weight is
labelled by abbb. We conclude that ae min and that an optimal schedule
is (abbb) ! .
7.4 The case
Two situations need to be considered: (i) the case u(a)
the case u(a) 2 ? l(a) 2 (with the case being
treated similarly).
Case
Assume that there exists an infinite heap w with an infinite number of each
piece and without any 'gap' at slots 1 and 3. Now, we focus on the second
slot of the heap w. The heights of the pieces a and b at slot 2 are given by
We set the ground shape to be
The heights of the pieces at slot 2 are now given by fnh a ; n 2 N   g and
g. Hence, the sequence of labels (read from bottom to top)
at slot 2 is the jump word w defined by (h a ; h b ; 0). Now, if we pile up
the pieces according to w, we indeed obtain a heap without any gap on
slots 1 and 3. An illustration is given in Figure 12. On slot 2, the pieces
have been shortened to facilitate their identification. If h a =h b is rational
a
a
a
a
a
a
Fig. 12. The optimal heap is the jump word babbaba \Delta \Delta \Delta .
then w is balanced and periodic and otherwise it is Sturmian. If h a =h b is
irrational, there does not exist any periodic optimal schedule. At last, we
have ae min The proof is exactly the same as in x7.1.
Case
Assume that u(a)
This contradicts the fact that a is bi-complete. We conclude that we have
and in the same way u(b)
Given there is a contact at slot 2 between the last two pieces
of the heaps xab and yab (resp. xba and yba) then
there is a contact at slot
2 between the last two pieces of the heap xab (resp. xba) then it is also the
case in the heap xaab (resp. xbba). It implies that
us set the ground shape to be I =
where the real L ? 0 is assumed to be large enough to
have a or b (see Figure 13 for an
It implies that the slot 2 is a contact slot for ab and ba; hence we
have We deduce that
We assume for the moment that h a =h b is irrational. Let x be the jump word
us assume that the infinite heap abx has no gap on slots 1 and
3. Then, the heights of the pieces on slot 2 are:
ffl lower part of piece a: fnh a \Gamma u(a)
ffl upper part of piece a: fnh a
ffl lower part of piece b: fnh b ; n 2 Ng;
ffl upper part of piece b: fnh b
Since h a =h b is irrational, by density of the points fnh b (mod h a ); n 2 Ng in
the interval [0; h a ], there exists a couple (p; q) 2 N 2 such that
ph a \Gamma u(a)
This is a violation of the piling mechanism, see Figure 13-(i) for an illustration.
Hence we conclude that there are some gaps on slot 1 or 3 in the heap abx.
Let l 1 be such that there is no gap at slots 1 and 3 in the heap abx[l 1
and there is a gap at slot 1 or 3 in the heap abx[l 1 In Figure 13-(i), we
have l be such that there is no gap at slots
1 and 3 in the heap bax[l there is a gap at slot 1 or 3 in the heap
2]. Note that we have l 1 - \Gamma1 and l 2 - \Gamma1, and that it is possible to
have l
Let us consider a heap abu (resp. bau), u 2 A   . There are three possible cases.
(1) There is no gap at slots 1 and 3 in the heap and
1). Let x n is the n-th letter of x. If
otherwise. Similarly we have '(IM(bax[l 2
and
a
a
I
a
a
a
a b
a
Fig. 13. (i) Heap
(2) There is no gap at slots 1 and 3 and u 6= x[juj]. In this case, we must
have
1). Assume we have , the case being treated
similarly. Since u 6= x[juj], in the heap x[n]b m a, there is a contact at slot 2
between the last two pieces. We conclude that '(IM(abx[n]b m
This case is illustrated in Figure 13-
(iii) where
(3) There is a gap somewhere in the heap at slot 1 or 3. This implies that
we have in the heap u a contact at slot 2 between a piece a and a piece b, or
between a piece b and a piece a. Considering the last couple (a; b) or (b; a) of
pieces in contact at slot 2, we obtain (for abu, the case bau is treated similarly)
where the heap abv, or bav, is such that there is no gap at slots 1 and 3.
The heap abv, or bav, is in one of the two cases (1) or (2) above. Case (3)
is illustrated in Figure 13-(ii) where
babab and
To summarize, we have proved that
The set '(H) is finite, hence we can apply the results of x3.2 to the contour-
completed automaton.
us assume that h a =h b is rational. We still consider the jump word x
with characteristics (h a ; h b ; 0), which is now periodic, see x4. If the heap abx
(or bax) has no gap on slots 1 and 3, then the schedule x is optimal (same
argument as in x7.1). If the heaps abx and bax both have a gap somewhere on
slot 1 or 3, the proof carries over exactly as in the case h a =h b 62 Q.
The structure of the countour-completed automaton can be deduced from the
above proof. For simplicity, we denote the state '(IM(w)) by w, and we
use the convention a there is a transition
abx[n] xn+1 \Gamma! abx[n + 1] and a transition abx[n] x 0
n+1 . For
there is a transition bax[n] xn+1 \Gamma! bax[n+ 1] and a transition bax[n] x 0
n+1 . In
ba
a
a a ab
abx[l1
a
a
Fig. 14. Outline of the contour-completed automaton.

Figure

14, we have represented an outline of the contour-completed automaton
in the case l 1 ? 0; l 2 ? 0 (ingoing and outgoing arrows as well as some arcs
are missing, and the multiplicities have been omitted).
Using the above analysis, we can get the value of the multiplicities in the
contour-completed automaton. Doing this, we obtain that there is a circuit
of minimal mean weight in the contour-completed automaton of label
with the conventions
Hence, one of the following schedules is optimal:
g. It remains to be proved that
are balanced.
We are going to prove that (bax[l 2 ]abx[l 1 ]) ! is balanced. We treat the case
If we have l 1 or l 2 equal to -1, the argument can be easily
adapted. Due to the definition of l 1 , the following intervals are all disjoint
(visually, they correspond to the portions of the second column occupied by
the pieces in the heap abx[l 1 ]. We consider open intervals in I a and closed
ones in I b in order to ensure that the first interval in I a and I b are indeed
I
I
In the same way, the following intervals are all disjoint (up to the minus sign,
they correspond to the portions of the second column occupied by the pieces
in the heap bax[l 2 ]):
I 0
An illustration of the intervals in I a ; I b ; I 0
a and I 0
b is provided in Figure 15-
(i)-(ii). Let us label the intervals in I a [ I 0
a by a and the ones in I b [ I 0
b by
b. If we read the sequence of labels from bottom to top, we obtain the word
~
is the mirror word of x[l 2 ] (the mirror word of the word
is the word ~
(by definition of l 1
and l 2 )
(n a h a
(\Gamman 0
a h a
a h a
Let us choose t 2 (\Gamman 0
a h a +l(a)
a h a )"[\Gamman 0
Let us consider the set
By construction, each real of S is in a different interval of I a ; I b ; I 0
a or I 0
b .
Hence, if we read the sequence of labels associated with S from bottom to
top, we obtain x[l Also by construction, we have t
a )h a 2
(n a h a
(i) (ii) (iii) (iv)
a
a a
a
\DeltaFig. 15. Illustration of the proof; here x[l 1
Let us set m a = n a
a and m
b . We define

Figure

15-(iii). By construction, we have either ( ) or (
for each n; n 0 such that 1 -
for each n; n 0 such that 1 -
Let us assume that (the case of Figure 15-(iii)). The other case is
treated similarly. Because of the property (  ), the sequence of a's and b's
corresponding to S is the same as the one corresponding to
Equivalently the jump words (h a
have the same prefix of length l 1 2. If we decide to
read double points as ba (see x4), then the jump word z with characteristics
is a balanced and periodic word, which is equal to
palindrome is a word equal to its mirror word. The above
construction shows that ~
is a palindrome (for instance, in Figure 15-
(iv), the sequences of a's and b's read from bottom to top, and top to bottom,
are the same). It implies that it is impossible to have l
x[l]abx[l] is
never a palindrome). By the same type of arguments, we can prove that x[l 1
and x[l 2 ] are also palindromes. Hence we have x[l 2 ]abx[l 1
and we conclude that (x[l 2 ]abx[l 1 ]ba) ! is balanced.
The fact that (abx[l 1 are balanced is proved in a similar way.
7.5 Greedy scheduling
We treat completely an instance of the jobshop described in the introduction,
see

Figure

1. The durations of the activities are assumed to be ff
4 \Theta ff); ff We assume that 1=15 ! ff ! 1=11. The
model corresponds to case (ii) in x7.4 above.
The contour-completed automaton of
in

Figure

16. The labels of the simple circuits are a; b; ba; ba 2 and ba 3 . Their
a j ff 51
a j ff
Fig. 16. Contour-completed automaton.
respective mean weights are ff 5 ; 1; 1=2; 1=3 and ff 15=4 . Hence the label of the
circuit of minimal mean weight is ba 2 if 4=45 - ff and ba 3 if ff - 4=45. We
conclude that an optimal schedule is
a
a
a
a
a
a b
a
a
a
a
a
a a
a
a
a
a
Fig. 17. Model with schedule and optimal schedule.
The greedy scheduling consists in always allocating the resource to the first task
which is ready to use it (i.e. w[n
have Here the greedy
schedule is always (ba 3 We conclude that greedy scheduling is suboptimal
in the case ff 2 (4=45; 1=11), see Figure 17.
This is in sharp contrast with a result from [23] xIV. There, the optimal
problem is studied for the model of Figure 1, but the authors consider a
slightly different criterion: minimization of the idle time of the resource. They
show that greedy schedules are indeed optimal for this criterion.
7.6 Ratio constraints
In [25,22,23], the authors were primarily interested in the following constrained
optimal problem: Find w 2 A ! minimizing lim n yH (w[n])=n while satisfying
In a manufacturing model, the motivation is to maximize the throughput while
meeting a given production ratio. For this constrained problem, and for the
model of Figure 1, it is proved in [22,23] that the optimal schedule is always
the jump word Two points are worth being noticed. First, the
optimal schedule is balanced and when fl 2 Q, it is of the form u ! where u is
the shortest balanced word meeting the ratio constraint. Second, the optimal
schedule does not depend on the timings of the model (ff

Figure

1).
These two properties depend heavily on the specific shape of the pieces in the
model of Figure 1. They are not satisfied in a general heap model with two
pieces, as shown below.
Example 17 Consider the model of Example 15. We look at the constrained
optimal problem with ratio 1=2. The optimal schedule of length 2n; n 2 N   ;
a a
a
a
Fig. 18. Optimal and worst schedule of ratio 1/2 and length 4.
is a n b n (or b n a n ) as illustrated on Figure 18. A possible optimal schedule is
balanced word with ratio 1=2 is optimal. Here,
the schedule (ab) ! , whose period is the shortest balanced word meeting the
constraint, is not an optimal but a worst case schedule! Examples in the same
spirit appear in [14], xVI-1 and in [20], x5.1.
8 Heap Models with Two Pieces: Average Case
In this section, products have to be interpreted in the field (R; +; \Theta). We
still assume that l(a) 6= u(a) and l(b) 6= u(b), otherwise the average problem
becomes trivial.
As in x7, the distinction between 'determinizable' and `non-determinizable'
automata is important. For the 'determinizable' case, it is easy to check that
the automata obtained in x7.1-7.4 are all irreducible. Hence we obtain ae E by
applying Prop. 6. Below, we illustrate this case on one example. There are two
cases where the heap automaton is 'non-determinizable', see x7. In one case,
we come up with an explicit formula for ae E and in the other case, we express
it as an infinite series.
Determinizable automaton. We consider the heap automaton H of x7.5.
Let fp(a); p(b)g be the probability distribution of the pieces. The contour-
completed automaton is represented in Figure 16. The corresponding transition
matrix is (see Prop. 6):
Its stationary distribution is
We conclude that we have, Prop. 6,
ae
This formula is valid for 1=15 ! ff ! 1=11, see x7.5. For instance, in the case
(the one of Figure 17), we have
ae E (H)
p(a)
ae
Case
space and let
independent random variables such that Pfx ag
and Pfx p(b). We set xH
and xH (n) 2 are transient random walks with respective drifts p(a)h a and
p(b)h b . We deduce immediately that ae E
Case 3g. We consider the case
simple but lengthy
computation provides the following formula (the details are available from
the authors on request). Let us denote by u (= u 1
We use the convention a
ae
One can obtain approximations of ae E (H) by truncating the infinite sums.
Computations of ae E for closely related models are carried out in [26].
9 Conclusion: Heap Models with Three or More Pieces
As recalled in the introduction, the optimal problem for a heap model with
an arbitrary number of rational pieces (8a 2 A;u(a); l(a) 2 Q R
solved
in [21]. In Theorem 14, the case of a heap model with two general pieces is
treated. We recall the results in the table below.
Characterizing optimal schedules is an open problem for models with three
pieces or more. Generalized versions of jump words appear naturally in some
models. Let be the alphabet. We consider ff
kg. We label the points fnff i by
a i and we consider the set [ k
in its natural order. The
infinite sequence of labels is called the (hypercubic) billiard sequence with
characteristics us consider the heap
model
Using an argument similar to the
one in x7.4, we obtain that the billiard sequence with characteristics
is an optimal schedule. A similar result is obtained for the heap model
Further research. During the reviewing process of this work, alternative
proofs of Theorem 14 as well as further developments have been proposed in
[30,11]. The methods in [11] also enable to refute the Lagarias-Wang finiteness
conjecture [27].

Acknowledgements

The authors thank Thierry Bousch, St'ephane Gaubert, Bruno Gaujal and
Colin Sparrow for stimulating discussions on the subject. The detailed comments
of an anonymous referee have also helped in improving the paper.



--R

Admission control in stochastic event graphs.
Optimal admission
Complexity of sequences defined by billiard in the cube.
Synchronization and Linearity.
Fractal Concepts in Surface Growth.
Complexity of trajectories in rectangular billiards.
Recent results on Sturmian words.
Rational Series and their Languages.
Sturmian words.
Personnal communication
Asymptotic height optimization for topical IFS
Evaluation de Performances d'une Classe de Syst'emes de Ressources Partag'ees.
Dynamics of synchronized parallel systems.
Timed Petri net schedules.
Describing industrial processes with interference and approximating their steady-state behaviour

Performance evaluation of (max

Task resource models and (max
Modeling and analysis of timed Petri nets using heaps of pieces.
Performance evaluation of timed Petri nets using heaps of pieces.
Optimal allocation sequences of two processes sharing a resource.


Extremal splittings of point processes.
Calcul de temps de cycle dans un syst'eme (max
The finiteness conjecture for the generalized spectral radius of a set of matrices.
Idempotent Analysis
Mots infinis en arithm'etique.
Optimal sequences in heap models.
Heaps of pieces
--TR
Tilings and patterns
Rational series and their languages
Timed Petri net schedules
Minimal (max,+) Realization of Convex Sequences
Automata, Languages, and Machines
Optimal Allocation Sequences of Two Processes Sharing a Resource
Mots infinis en arithmMYAMPERSANDeacute;tique

--CTR
Pascal Hubert , Laurent Vuillon, Complexity of cutting words on regular tilings, European Journal of Combinatorics, v.28 n.1, p.429-438, January 2007
Sylvain Lombardy , Jacques Sakarovitch, Sequential?, Theoretical Computer Science, v.356 n.1, p.224-244, 5 May 2006
timed Petri net;optimal scheduling;heap of pieces;+ semiring;sturmian word;tetris game;automaton with multiplicities