A Partial Order Representation of Processes of Transforming Graphs

Article type: Research Article

Authors: Maggiolo-Schettini, Andrea | Winkowski, Józef

Affiliations: Dipartimento di Informatica, Università di Pisa, 56 125 Pisa, Corso Italia 40, Italy. maggiolo@di.unipi.it | Instytut Podstaw Informatyki PAN, Ordona 21, 01-237 Warszawa, Poland. wink@ipipan.waw.pl

Abstract: A model of processes of transforming graphs is proposed in which concurrency and branching can be represented. Operations on structures representing processes of transforming graphs are defined that allow one to construct such structures from simple components and to characterize sets of processes of transforming graphs, including sets of processes generated by graph grammars.

Keywords: graph, occurrence structure, dynamic graph, application of a dynamic graph to a graph, concatenation of dynamic graphs, sum of dynamic graphs, production, derivation, graph grammar

DOI: 10.3233/FI-1997-313407

Journal: Fundamenta Informaticae, vol. 31, no. 3-4, pp. 337-355, 1997