Parallel composition and unfolding semantics of graph grammars

Abstract

The main aims of this thesis are to provide an approach to the parallel composition of graph grammars and a semantics for graph grammars, called the unfolding semantics, in which the aspects of concurrency and compositionality with respect to the parallel composition play a central role. The parallel composition of graph grammar allows the composition of grammars with respect to a shared part (that may be empty), and is based on parallel and amalgamated composition of the rules of the component grammars. Moreover, the result of the composition is suitably syntactically and semantically related to the component grammars. The unfolding semantics of a graph grammar is a true concurrent, branching structure semantics in which states (graphs) as well as changes of states (derivations) are represented. The unfolding can be constructed incrementally, and we show that this yields the same result as a construction based on gluing of the deterministic computations of a grammar. Moreover, the unfolding of a graph grammar is itself a graph grammar that belong to a special class of graph grammars: the occurrence graph grammars. Here this class is defined axiomatically, and the members of this class can be seen as grammars that represent (deterministic and non-deterministic) computations of another grammars. The semantics of a grammar obtained as the parallel composition of other grammars is isomorphic to the composition of the semantics of the component grammars. As the purpose of the parallel composition is to be a composition for concurrent and reactive systems, the fact that this composition is compatible with a true concurrency semantics is an attractive result.

Das Hauptziel dieser Arbeit ist es, einen Ansatz fur die parallele Komposition von Graph- Grammatiken und eine Unfolding-Semantik genannte Semantik fiir Graph-Grammatiken bereitzustcllen, in der die Aspekte Nebenlaufigkeit und Kompositionalitat bzgl. der parallelen Komposition eine zentrale Rolle einnehmen. Die parallele Komposition von Graph-Grammatiken erlaubt die Komposition von Grammatiken bzgl. eines gemeinsamen (moglicherweise leeren) Anteils und basiert auf der parallelen und amalgamierten Komposition von Regeln der komponierten Grammtiken. Dariiber hinaus ist das Kompositionsergebnis syntaktisch und semantisch in geeigneter Weise mit den komponierten Grammatiken verkniipft. Die Unfolding-Semantik einer Graph-Grammatik ist eine echt nebenldufige, verzweigende Semantik, in der sowohl Zustande (Graphen) als auch Zustandsanderungen (Ableitungen) reprasentiert sind. Das Unfolding kann inkrementell konstruiert werden und es wird gezeigt, daß dies das gleiche Result liefert wie die Verklebung der deterministischen Berechnungen einer Grammatik Dartiberhinaus ist das Unfolding einer Graph-Grammatik selbst eine Graph- Grammatik, die einer speziellen Klasse von Graph-Grammatiken angehOrt: den Occurrence- Grammatiken. Hier wird diese Klasse axiomatisch definiert und die Elemente dieser Klasse kOnnen als Grammatiken gesehen werden, die (deterministische und nicht-deterministische) Berechnungen einer anderen Grammatik reprdsentieren. Die Semantik einer Grammatik, die aus der parallelen Komposition anderer Grammatiken entstanden ist, ist isomorph zur Komposition der Semantiken der komponierten Grammatiken. Dieses Kompatibilitatsresultat verbindet die parallele Komposition und die Unfolding Semantik in enger Weise. Da der Zweck der parallelen Komposition die Komposition nebenldufiger Systeme ist, stellt die Kompatibiliat von Komposition und Nebenlaufigkeitssemantik ein attraktives Ergebnis dar.