Concurrent Transformations of Relational Structures

Article type: Research Article

Authors: Ehrig, Hartmut^a | Habel, Annegret^a | Rosen, Barry K.^b

Affiliations: [a] Fachbereich Informatik, Technische Universität Berlin, 1000 Berlin 10, F.R.G. | [b] Computer Sciences Department, IBM T.J.W. Research Center, Yorktown Heights, N.Y., U.S.A.

Abstract: This paper provides a common framework to study transformations of structures ranging from all kinds of graphs to relational data structures. Transformations of structures can be used as derivations of graphs in the sense of graph grammars, as update of relations in the sense of relational data bases, or even as operations on data structures in the sense of abstract data types. The main aim of the paper is to construct parallel and concurrent transformations from given sequential ones and to study sequentializability properties of complex transformations. The main results are three fundamental theorems concerning parallelism, concurrency and decomposition of transformations of structures. On one hand these results can be considered as a contribution to the study of con currency in graph grammars and on the other hand as a formal framework for consistent concurrent update of relational structures.

DOI: 10.3233/FI-1986-9103

Journal: Fundamenta Informaticae, vol. 9, no. 1, pp. 13-49, 1986