Studies on graph grammars : comparison of various models and applications to graph theory

Abstract

In this short chapter we shall raise a few questions whose answers could throw further light on the theory of graph grammars. When the notion of contextual condition was introduced by Rosenfeld, the grammars were constructed with each rule allowing a question to be answered before its application. In short, the applicability condition is verified locally and then the rule would be applied. This verification itself may be highly complicated. Since there are quite a few conditions whose verification algorithms are of exponential complexity, one would ideally prefer to do away with the contextual or applicability condition. Montanari (1970) eliminates the applicability conditions by giving a construction for an equivalent grammar in which the applicability condition is always true. That means the contextual?condition part can be totally ignored. But the construction yields a graph grammar whose type need not be the same as the type of the original graph grammar. For example, a normal grammar may lose its property of normalcy. So the first important question we would like to raise is regarding the potentialities of contextual conditions. In view of the above discussions, we may ask the following questions:

For any given graph grammar of type T, can we construct a graph grammar of the same type T without contextual conditions?

If not, how does the generating power vary with the contextual condition?

Even in specifying the contextual condition, we could speak of finer classifications. The verification of the contextual condition locally might involve algorithms whose complexity can range from linear to exponential. Can we then stratify the class with the complexity of algorithms for verifying the contextual conditions? That is, consider:

The class of languages created by contextual conditions whose verification takes linear time, and The class of languages created by graph grammars whose rules contain contextual conditions whose verification takes polynomial or exponential time.

Do these classes (1) and (2) form a hierarchy? Do they give us a countable collection of graph?language classes forming an ascending chain with respect to inclusion? That is, if we denote by GL?, k ? 1, the class of graph languages generated by graph grammars whose rules contain contextual conditions whose verification takes time of order n?, and GL???, the class of graph languages generated by grammars whose contextual?condition verification takes exponential time, does the following hold good? GL1?GL2???GLk???GLexpGL_1 \subseteq GL_2 \subseteq \cdots \subseteq GL_k \subseteq \cdots \subseteq GL_{exp}GL1??GL2????GLk????GLexp? A study of this would help us analyse the complexity involved in the generation of a particular class of graphs where the grammar has contextual conditions. Till now, no complexity measure has been proposed for the tasks involved in graph grammars. Can the above classification bring out the inherent complexity involved in the generation of a particular class? If not, how can we define reasonably good complexity measures? The notion of complexity measures for graph grammars should be given great attention in view of the wider range of applications to the theory of graph grammars. A fruitful study on these topics should enrich and strengthen the theoretical framework of this fast?growing field. Although computational complexity of generation of a graph by a grammar is not discussed, the complexity issues regarding the membership problem have been solved recently for a few classes in Brandenburg (1983). Referring to Chapter 4 of our thesis, we find several issues are still to be solved. First, we have considered only linear and context?free types of various models; a detailed comparison at the level of context?sensitive and monotone types would be highly valuable in demonstrating the powers of various models. The basic mechanisms involved in each model have certain capabilities and limitations. We have only seen the tip of the iceberg. To appreciate the nature of the embedding scheme in its full force, we should compare powerful types like CS–AGG or CS–JGG, etc., which has important applications in highlighting various aspects of each model. Even among context?free types of these different models we see disparities ranging from incomparability to equality. This shows we should not treat the embedding mechanism as merely a means to generate graphs; it truly determines the characteristics of the classes of graphs produced. Edge?replacement systems and vertex?replacement systems exhibit different characteristics. In this context, it is appropriate to remark that we should aim at constructing automata or recognizing devices for a class of graphs or a type of graph grammar (see, for example, Wu et al., 1979). A complete development of such mechanisms could bring out the intrinsic nature of the grammar as well as the structure of the resulting classes of graphs. This could also lead to reasonably good complexity measures and ease the comparison of different models.