Concurrent Computing: from Petri Nets to Graph Grammars

Abstract

Petri nets are widely accepted as a specification formalism for concurrent and distributed systems. One of the reasons of their success is the fact that they are equipped with a rich theory, including well-understood concurrent semantics; they also provide an interesting benchmark for tools and techniques for the description of concurrent systems. Graph grammars can be regarded as a proper generalization of Petri nets, where the current state of a system is described by a graph instead as by a collection of tokens. In this tutorial paper I will review some basic definitions and constructions concerning the concurrent semantics of nets, and I will show to what extent corresponding notions have been developed for graph grammars. Most of such results come out from a joint research by the Berlin and Pisa COMPUGRAPH groups.