TITLE:
Asymptotic Analysis of Heaps of Pieces and application to Timed Petri Nets

AUTHORS: 
St\'ephane Gaubert
INRIA 
Domaine de Voluceau, B.P.~105
 78153 Le Chesnay Cedex, France
Stephane.Gaubert@inria.fr

and 

Jean Mairesse
LIAFA
CNRS-Universit\'e Paris 7
Case 7014, 2 place Jussieu
75251 Paris Cedex 05, France
mairesse@liafa.jussieu.fr

ABSTRACT
What is the density of an infinite heap of pieces, if we let pieces
fall down randomly, or if we select pieces to maximize the density? 
How many transitions of a safe timed Petri net can we fire
per time unit? 
We reduce these questions to the computation of the average and
optimal case Lyapunov exponents of max-plus automata,
and we present several techniques to compute these exponents.
First, we introduce a completed ``non-linear automaton'',
which essentially fills incrementally all the gaps that can be filled
in a heap without changing its asymptotic height.  
Using this construction, when the pieces have integer valued shapes, and
when any two pieces overlap, the Lyapunov exponents can be explicitly computed.
We present two other constructions (partly based on Cartier-Foata normal 
forms of traces) which allow us to compute the optimal case Lyapunov exponent,
assuming only that the pieces have integer valued shapes.

KEYWORDS

Heaps of pieces, Tetris game, safe timed Petri nets,
max-plus semiring, automaton with multiplicities, Lyapunov exponents.