GRAPH PROCESSES

Article type: Research Article

Authors: Corradini, A. | Montanari, U. | Rossi, F.

Affiliations: Università di Pisa, Dipartimento di Informatica, Corso Italia 40, 56125 Pisa, Italy. E-mail: {andrea,ugo,rossi}@di.unipi.it

Abstract: We first give a new definition of graph grammars, which, although following the algebraic double-pushout approach, is more general than the classical one because of the use of a graph of types where all involved graphs are mapped to. Then, we develop a process-based semantics for such (typed) graph grammars, in the line of processes as normally used for providing a semantics to Petri nets. More precisely, we represent each equivalence class of derivations as a graph process, which can be seen as an acyclic graph grammar, plus a mapping of its items onto the items of the given grammar. Finally, we show that such processes represent exactly the equivalence classes of derivations up to the well-known shift-equivalence, which have always been used in the literature on graph grammars. Therefore graph processes are attractive alternative representatives for such classes. The advantage of dealing with graph processes instead of equivalence classes (or also representatives belonging to the equivalence classes) is that dependency and/or concurrency of derivation steps is explicitly represented.

DOI: 10.3233/FI-1996-263402

Journal: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 241-265, 1996