Abstract processes of place/transition systems

DOI10.1016/J.IPL.2011.03.013MaRDI QIDQ1944098zbMATH OpenOpenAlexFDO

Authors Jens-W. Schicke, Rob van Glabbeek, Ursula Goltz

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.5916

zbMATH Keywords

concurrencyPetri netsprocessesP/T systemscausal semantics

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.

Recommendations

• Abstract processes and conflicts in place/transition systems
• On causal semantics of Petri nets (extended abstract)
• scientific article; zbMATH DE number 4035157
• scientific article; zbMATH DE number 1799516
• scientific article; zbMATH DE number 1337730

Cites work

• scientific article; zbMATH DE number 17833 (Why is no real title available?)
• A trace semantics for Petri nets
• Axiomatizing the algebra of net computations and processes
• Branching processes of Petri nets
• CONCUR 2005 – Concurrency Theory
• Configuration structures, event structures and Petri nets
• Executions: A new partial-order semantics of Petri nets
• On the semantics of place/transition Petri nets
• Petri nets, event structures and domains. I
• The non-sequential behaviour of Petri nets

Cited in

(9)

• Abstract processes in the absence of conflicts in general place/transition systems
• Comparative trace semantics of time Petri nets
• CCS: it's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions
• Modelling mutual exclusion in a process algebra with time-outs
• Just testing
• scientific article; zbMATH DE number 7453963 (Why is no real title available?)
• Abstract processes and conflicts in place/transition systems
• On causal semantics of Petri nets (extended abstract)
• Synchronous and asynchronous communication(s) between three parties

This page was built for publication: Abstract processes of place/transition systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944098)