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.