Zero-safe nets: The individual token approach

Abstract

In this paper we provide both an operational and an abstract concurrent semantics for zero-safe nets under the individual token philosophy. The main feature of zero-safe nets is a primitive notion of transition synchronization. Besides ordinary places, called stable places, zero-safe nets come equipped with zero places, which are empty in any stable marking. Connected transactions represent basic atomic computations of the system between stable markings. They must satisfy two main requirements: 1) to model interacting activities which cannot be decomposed into disjoint sub-activities, and 2) not to consume stable tokens which were generated in the same transaction. Zero tokens acts as triggers for the firings of the transitions which compose the transaction. The abstract counterpart of a zero-safe net consists of a P/T net where each transition locates a distinguished transaction. In the second part of the paper, following the Petri nets are monoids approach, we make use of category theory to analyze and motivate our framework. More precisely, the operational semantics of zero-safe nets is characterized as an adjunction, and the derivation of abstract P/T nets as a coreflection.

Research supported by Office of Naval Research Contracts N00014-95-C-0225 and N00014-96-C-0114, National Science Foundation Grant CCR-9633363, and by the Information Technology Promotion Agency, Japan, as part of the Industrial Science and Technology Frontier Program “New Models for Software Architechture” sponsored by NEDO (New Energy and Industrial Technology Development Organization). Also research supported in part by U.S. Army contract DABT63-96-C-0096 (DARPA); CNR Integrated Project Metodi e Strumenti per la Progettazione e la Verifica di Sistemi Eterogenei Connessi mediante Reti di Comunicazione; and Esprit Working Groups CONFER2 and COORDINA. Research carried on in part while the second author was on leave at Computer Science Laboratory, SRI International, Menlo Park, USA, and visiting scholar at Stanford University.