TY - GEN
T1 - Asymptotic analysis of heaps of pieces and application to timed Petri nets
AU - Gaubert, Stephane
AU - Mairesse, Jean
N1 - Publisher Copyright:
© 1999 IEEE.
PY - 1999/1/1
Y1 - 1999/1/1
N2 - 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.
AB - 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.
U2 - 10.1109/PNPM.1999.796562
DO - 10.1109/PNPM.1999.796562
M3 - Conference contribution
AN - SCOPUS:84926150675
T3 - Proceedings - 8th International Workshop on Petri Nets and Performance Models, PNPM 1999
SP - 158
EP - 169
BT - Proceedings - 8th International Workshop on Petri Nets and Performance Models, PNPM 1999
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 8th International Workshop on Petri Nets and Performance Models, PNPM 1999
Y2 - 8 September 1999 through 10 September 1999
ER -