1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Backward coupling in petri nets

  • @INPROCEEDINGS{10.1145/1190095.1190137,
        author={Anne  Bouillard and Bruno  Gaujal},
        title={Backward coupling in petri nets},
        proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
        keywords={Petri nets perfect simulation (max plus) algebra},
  • Anne Bouillard
    Bruno Gaujal
    Year: 2012
    Backward coupling in petri nets
    DOI: 10.1145/1190095.1190137
Anne Bouillard1,*, Bruno Gaujal2,*
  • 1: Institute of Communication engineering, National Tsinghua University, 101, Kuangfu Rd, S. 2, Hsinchu, 300, Taiwan.
  • 2: INRIA, Lab. ID-IMAG (CNRS, INPG, INRIA, UJF), 51, Av. J. Kunztmann, Montbonnot, France.
*Contact email: Anne.Bouillard@ens-lyon.fr, Bruno.Gaujal@imag.fr


In this paper, we show how to design a perfect sampling algorithm for stochastic Free-Choice Petri nets by backward coupling. For Markovian event graphs, the simulation time can be greatly reduced by using extremal initial states, namely blocking marking, although such nets do not exhibit any natural monotonicity property. Another approach for perfect simulation of non-Markovian event graphs is based on a (max,plus) representation of the system and the theory of (max,plus) stochastic systems. Next, we show how to extend this approach to one-bounded free choice nets to the expense of keeping all states. Finally, experimental runs show that the (max,plus) approach needs a larger simulation time than the Markovian approach.