Concurrent Derivations as Single Pushout Graph Grammar Processes
✍ Scribed by Martin Korff; Leila Ribeiro
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 688 KB
- Volume
- 2
- Category
- Article
- ISSN
- 1571-0661
No coin nor oath required. For personal study only.
✦ Synopsis
Algebraic graph transformations visually support intuition, have a strong theoretical basis, and provide a formal, implementation independent basis for the description of discretely evolving computational systems and their formal and tractable analysis. Graph grammar models of concurrent systems (petri nets, actor systems) have i nspired corresponding semantics developments. Recently this led to the introduction of partial orders of concurrent derivations (concurrent computations). A concurrent derivation (CDer) abstracts from the (sequential) order of rule applications in the sequential derivation and thus can be considered as a concurrent process. Complementary, a morphism between two concurrent derivations expresses that the rst is a computational approximation of the second. In this paper we newly introduce non-deterministic concurrent derivations (CTrees) as classes of concurrently equivalent sequential derivation trees. Due to the fact that also in nite computations are represented by C T rees, the category of all CTrees of a given graph grammar has a nal object (the concurrent counterpart of the whole sequential tree of the given grammar) which i s a p p r o ximated by all other CTrees. We show that (syntactical) morphisms between two graph grammars induce corresponding adjunction between the corresponding (semantic) categories of CDers and CTrees respectively.