Aspects of the implementation of sequential graph rewriting systems
Philip M. Dorin · 1982
A sequential graph rewriting system (sequential GRS) is a formal mechanism for producing sequences of directed graphs, and is composed of an initial graph, from which other graphs are derivable, and a set of rewriting rules, which guide the derivation process. In applications, each graph is considered to be the representation of some stage in the development of an organism or system; a sequence of derived graphs represents the time-ordering of the development. Within computer science, applications have arisen from studies of record-handling, program development, computer and semantic networks. Additionally, various biological, chemical, and sociological systems can be modeled in terms of sequential GRSs. The research described herein concerns the design and implementation of a computational environment within which sequential GRSs can be programmed. Following a review of the theory of sequential GRSs, a general approach to the implementation problem is presented: each sequential GRS is viewed as a program to be executed on a single, specialized architecture. A user-oriented Graph Programming Language (GPL), and a system for constructing and executing these programs (the GPL machine) are developed. The realization of this system is accomplished in software, and is based on structures of classical computer systems architecture and on the concept of string-grammar architectures. A primary focus of this research is the engineering of GPL and the GPL machine. Many design problems have been identified and resolved; where appropriate, various heuristics have been tested for their effect on system performance, and several examples of the use of the system are included. A concluding chapter deals with experiences gained from the present GPL system, and suggests further refinements.