Synthesis of Nets with Step Firing Policies (2008)

Author(s): Darondeau P, Koutny M, Pietkiewicz-Koutny M, Yakovlev A

    Abstract: The unconstrained step semantics of Petri nets is impractical for simulating and modelling applications. In the past, this inadequacy has been alleviated by introducing various flavours of maximally concurrent semantics, as well as priority orders. In this paper, we introduce a general way of controlling step semantics of Petri nets through step firing policies that restrict the concurrent behaviour of Petri nets and so improve their execution and modelling features. In a nutshell, a step firing policy disables at each marking a subset of enabled steps which could otherwise be executed. We discuss various examples of step firing policies and then investigate the synthesis problem for Petri nets controlled by such policies. Using generalised regions of step transition systems, we provide an axiomatic characterisation of those transition systems which can be realised as reachability graphs of Petri nets controlled by a given step firing policy. We also provide a decision and synthesis algorithm for PT-nets and step firing policies based on linear rewards of steps, where fixing the reward of elementary transitions is part of the synthesis problem. The simplicity of the algorithm supports our claim that the proposed approach is practical.

      • Date: March 2008
      • Series Title: School of Computing Science Technical Report Series
      • Pages: 25
      • Institution: School of Computing Science, University of Newcastle upon Tyne
      • Publication type: Report
      • Bibliographic status: Published

      Keywords: Petri nets, step firing policy, step transition system, regions, synthesis problem

      Staff

      Professor Maciej Koutny
      Professor of Computing Science

      Dr Marta Pietkiewicz-Koutny
      Lecturer

      Professor Alex Yakovlev
      Professor of Computer System Design