Research On Context-Sensitive Graph Grammars And Their Applications

Visual Languages that offer a means to represent the structure and composition of complex objects in a visual, intuitive, and abstract manner, have been widely adopted in computer-related disciplines. One of the most fundamental questions in visual language research is how to specify a visual language. Naturally, graph grammars are appropriate formalisms for the specification of visual languages, much the same as formal grammars have been utilized to specify textual languages. Context-sensitive graph grammars are the primary choice for achieving this goal, as context-free ones suffer deficiencies in usability and expressivenesss. Nevertheless, there are drawbacks in many aspects of the existing context-sensitive graph grammar formalisms. Research on many fundamental issues is still confronted with challenges, including the following aspects:(I) Absence of theoretical comparison of expressive powers between the context-sensitive formalisms; (II) deficiency in intuitivenesss of productions in implicit formalisms that is originated from the shortage of explicit contexts in productions; (â…¢) the existing two classes of parsing algorithms are either confined to confluent graph grammars, or computationally inefficient. A general concept framework for context-sensitive graph grammars is proposed to accommodate most of the existent formalisms. On the basis of the framework, a systematic study of these challenges is presented in the dissertation, which includes the following efforts:1. Based on the result of a comprehensive analysis and induction of the essential properties of context-sensitive graph grammar formalisms, the relationships between their expressive powers are revealed and proved by constructing algorithms to implement the transformations between graph grammar instances of these formalisms. On the one hand, the conclusions on their expressiveness theoretically supplement the hierarchy of graph language classes generated by graph grammars. On the other, the proposed algorithms can correlate these context-sensitive formalisms, thus facilitating the usage of them, as distinct formalisms rather than merely one can be chosen to respectively specify and parse visual objects in applications.2. To tackle the deficiency in intuitivenesss of productions in implicit formalisms, a theory of contexts and a method for context computation based on the RGG formalism are presented to reveal contexts that are implicitly contained in productions. On the concepts of partial and total precedence relation between productions, a formal definition of contexts is proposed, the essential properties and a sufficient condition for the existence of contexts are characterized, and a connection between contexts and context instances is established theoretically. Several algorithms for context computation are provided accordingly. The exploitation of originally implicit contexts can improve the intuitivenesss of productions, and thus facilitate the comprehension and design of graph grammars. Moreover, this method can be effortlessly generalized to other implicit formalisms.3. Two classes of approaches are proposed to improve the parsing algorithms. To boarden the application scope of the parsing algorithms that are narrowly confined to confluent graph grammars, two distinct approaches based on the RGG formalism are proposed to transform a non-confluent set of producitons into a confluent set such that the graph languge of the former is preserved in the latter. In the first approach, an extended RGG formalism called XRGG is proposed, and then an algorithm is developed to transform a non-confluent set of RGG productions into a confluent set of XRGG productions. The second approach is based on contexts. The productions that lead to a non-confluent graph grammar are chosen, and each of them is replaced by the one that is created by equipping it with all the level-1 contexts and their derivative contexts in a tailored form. These two approaches can be applied in different scenarios. Moreover, to improve the efficiency of the general parsing algorithms, an approach that employs context-matching is presented. It can preclude unnecessary reductions in the process of parsing by conducting extra matches between the context graph of a redex in a host graph and the contexts of the corresponding production, so as to improve parsing performance.4. An application of context-sensitive graph grammars in parallel exploitation is discussed. To cope with the challenge that parallel exploitation techniques commonly demand some dependency graphs of programs as a prerequisite, a task-level parallel programming graph language GPPL is defined based on the RGG formalism, to directly describe the control and data flow graphs of serial or parallel programs, and then two algorithms are presented to detect parallelism of GPPL graph programs. In comparison to the existing graph languages for specifying programs and the associated algorithms for parallel analyzing, GPPL is more succinct, intuitive, and expressive, and the proposed algorithms are more powerful in parallel exploitation.5. A supporting system for context-sensitive graph grammars is designed and partially implemented, which can be used as a platform for the design, parsing and application of graph languages on the basis of context-sensitive graph grammars. This system provides a graphical user interface for editing graph grammars, offers the capabilities for checking the syntax and computing the contexts of a graph grammar, and renders the mechanism for deciding whether a graph grammar is confluent or not, and then parsing host graphs using different algorithms accordingly. Moreover, the GPPL is implmented and the parsing of a GPPL graph is demonstrated in the supporting system.