Structure graph grammars and structure graph automata

Ph.D.In this thesis we undertake a study of formal three-dimensional representational and acceptor methods. In lieu hereof then, we give a short overview of such strategies existing in the literature. Graph and graph grammar theory present us with a powerful two dimensional representational method, and we propose to extend these concepts to the three-dimensional case. We therefore give a short discussion on the theory of graphs and graph grammars. As point of departure, we review the concepts of a structure parameter and structure graph (SG) introduced by us in [BEH,93] and show that these concepts enable us to describe objects in three-dimensional space. We propose various modified graph grammar extensions that generates structure graphs, referred to as Structure Graph Grammar extensions (SGG's) by combining context provisions with the rewriting rules of the various grammar systems. This proposed methodology of ours culminates in the combination of production rule bounded contexts and globally specified contexts, thus defining Structure Graph Grammar extension 7 (SGG-7). We show the applicative value of the three dimensional generative abilities of SGG's by considering the generation of various chemical structural formulae. Brandenburg and Skodinis mentions in [BS,95] that there is a shortcoming in the theory of graph grammars in the sense that in general, there exists no accepting device for graph grammar systems. The following quote from [BS,95,p.336] illustrates this point: "There are no graph automata, which fit to the major classes of graph languages. This is a gap in the theory of graph languages." Regarding the class of languages generated by SGG-7, we propose to fill this gap by introducing an Structure Graph Automaton (SGA) to accept this class of languages