GRAPH GRAMMARS WITH NEGATIVE APPLICATION CONDITIONS

Article type: Research Article

Authors: Habel, Annegret | Heckel, Reiko | Taentzer, Gabriele

Affiliations: Department of Mathematics and Computer Science, University of Bremen, D-28334 Bremen, Germany | Computer Science Department, Technical University of Berlin, D-10587 Berlin, Germany

Abstract: In each graph-grammar approach it is defined how and under which conditions graph productions can be applied to a given graph in order to obtain a derived graph. The conditions under which productions can be applied are called application conditions. Although the generative power of most of the known general graph-grammar approaches is sufficient to generate any recursively enumerable set of graphs, it is often convenient to have specific application conditions for each production. Such application conditions, on the one hand, include context conditions like the existence or non-existence of nodes, edges, or certain subgraphs in the given graph as well as embedding restrictions concerning the morphisms from the left-hand side of the production to the given graph. In this paper, the concept of application conditions introduced by Ehrig and Habel is restricted to contextual conditions, especially negative ones. In addition to the general concept, we state local confluence and the Parallelism Theorem for derivations with application conditions. Finally we study context-free graph grammars with application conditions with respect to their generative power.

Keywords: graph grammars, graph transformation systems, application conditions, contextual conditions

DOI: 10.3233/FI-1996-263404

Journal: Fundamenta Informaticae, vol. 26, no. 3-4, pp. 287-313, 1996