In: Petri Net Newsletter No. 56, pages 17-26. April 1999.
Abstract: Synchronization graphs, marked graphs, or more precisely T-systems, constitute an important class of Petri nets well suited for the description and analysis of concurrent but deterministic synchronization schemes. T-systems are a well investigated model of net theory with a rich collection of theoretical results. Nevertheless it has recently been found by the author that a fundamental problem concerning the nature of concurrency and causality has not been addressed so far, namely the questions if there exists another binary relation between net elements not covered by concurrency and causality in safe and live T-systems. Here we will give a negative answer by proving that every two elements are either concurrent or causally dependent (tertium non datur). Another issue that has not received much attention so far is the notion of security introduced by C.A. Petri with the motivation that it provides a more adequate abstraction of technical safety than the usual notion of safety in net theory. As an application of the first result on the nature of concurrency and causality we will prove that a surprisingly simple structural criterion for security proposed by C.A. Petri and C.Y. Yuan actually provides a characterization of security in safe and live T-systems.
Keywords: Petri nets, synchronization graphs, marked graphs, T-systems, causality, concurrency, safety, security.