*For the most recent entries see the
Petri Nets Newsletter.*

## Asymptotic analysis of heaps of pieces and application to timed Petri nets.

Gaubert, S.;
Mairesse, J.
In:
*Proc. 8th Int. Workshop on Petri Net and Performance Models (PNPM'99), 8-10 October 1999, Zaragoza, Spain*, pages 158-169.
1999.

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:
Lyapunov exponents, Tetris game, automaton with multiplicities, heaps of
pieces, max-plus semiring, safe timed Petri nets.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*