Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T12:18:57.637Z Has data issue: false hasContentIssue false

Algebraic properties of processes for Local Action Systems

Published online by Cambridge University Press:  16 September 2002

NICO VERLINDEN
Affiliation:
Department of Mathematics and Computer Science, U.I.A. Universiteitsplein 1, B-2610 Antwerp, Belgium Email: {Nico.Verlinden,Dirk.Janssens}@ua.ac.be
DIRK JANSSENS
Affiliation:
Department of Mathematics and Computer Science, U.I.A. Universiteitsplein 1, B-2610 Antwerp, Belgium Email: {Nico.Verlinden,Dirk.Janssens}@ua.ac.be

Abstract

Graph rewriting has been used extensively to model the behaviour of concurrent systems and to provide a formal semantics for them. In this paper, we investigate processes for Local Action Systems (LAS); LAS generalize several types of graph rewriting based on node replacement and embedding. An important difference between processes for Local Action Systems and the process notions that have been introduced for other systems, for example, Petri nets, is the presence of a component describing the embedding mechanism. The aim of the paper is to develop a methodology for dealing with this embedding mechanism: we introduce a suitable representation (a dynamic structure) for it, and then investigate the algebraic properties of this representation. This leads to a simple characterization of the configurations of a process and to a number of equational laws for dynamic structures. We illustrate the use of these laws by providing an equational proof of one of the basic results for LAS processes, namely that the construction yielding the result graph of a process behaves well with respect to the sequential composition of processes.

Type
Research Article
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was partially supported by the EC TMR Network GETGRATS (General Theory of Graph Transformation Systems) and Esprit Working Group APPLIGRAPH through Universitaire Instelling Antwerpen.
This paper is a complete and revised version of a lecture given at the workshop on Theory and Applications of Graph Transformations (GRATRA 2000), which was a satellite event of ETAPS 2000 in Berlin, March 2000.