Trustworthy Systems

Abstract processes and conflicts in place/transition systems

Authors

Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke-Uffmann

DATA61

Technical University of Braunschweig

UNSW Sydney

Abstract

For one-safe Petri nets or condition/event-systems, a process as defined by Carl Adam Petri provides a notion of a run of a system where causal dependencies are reflected in terms of a partial order. Goltz and Reisig have generalised this concept for nets where places carry multiple tokens, by distinguishing tokens according to their causal history. However, this so-called individual token interpretation is often considered too detailed. Here we identify a subclass of Petri nets, called structural conflict nets, where no interplay between conflict and concurrency due to token multiplicity occurs. For this subclass, we define abstract processes as equivalence classes of Goltz-Reisig processes. We justify this approach by showing that there is a largest abstract process if and only if the underlying net is conflict-free with respect to a canonical notion of conflict.

BibTeX Entry

  @article{vanGlabbeek_GS_toappear,
    author           = {van Glabbeek, Robert and Goltz, Ursula and Schicke-Uffmann, Jens-Wolfhard},
    doi              = {https://doi.org/},
    journal          = {Information and Computation},
    keywords         = {Concurrency; Petri nets; {PT}-systems; causal semantics; processes.},
    paperurl         = {https://trustworthy.systems/publications/full_text/vanGlabbeek_GS_toappear.pdf},
    publisher        = {Elsevier},
    title            = {Abstract Processes and Conflicts in Place/Transition Systems},
    year             = {To appear}
  }

Download