A system of graph grammars which generates all recursively enumerable sets of labelled graphs
Tadahiro Uesu · Tsukuba Journal of Mathematics · 1978
The aim of this paper is to prove that the system of simple graph grammars (Einfache Graph-Grammatiken) in[1]is complete. A graph grammar is a generalization of a Chomsky-grammar which defines a graph language, i.e。a language composed of a set of directed graphs with labelled nodes and arcs。 A system of graph grammars is said to be complete if it satisfies the following property: For each finite set T of labels, the class of all graph languages over T defined by graph grammars of the system is identical with the class of ail recussively enumerable sets of labelled graphs over T. Where a set of labelled graphs over T is recursively enumerable if the associated set of integers by a Godel numbering from the labelled graphs over T into the integers is recursively enumerable。 Several authors have introduced their system of graph grammars (e・g.[11,[21, [31,[41,[51,[6j,[7])。However they did not refer to the completeness of their systems。 The system of simple graph grammars was introduced in[1]as a subsystem of the system in [2]。In this paper we modify the definition of the system in the following manner: A production of our system is an ordered triple(K,F,K’)which consists of two labelled graphs 瓦A7 and a one・to・one function F from a set of nodes of 瓦to a set of nodes of K'. If iK, F, m is a production, and if K occurs in a labelled graph G, then the production is applicable to G, and the effect of the application is to replace an occurrence of K in G by 瓦へ The function F specifies the embedding of 瓦7into the remainder of removing K from G; if a node n' of K' is the image of a node n of K, thenがis put upon the trace of n in the remainder. This is illustrated by Figure O。 The formal definitions of labelled graphs and several concepts with labelled graphs are given in the first section of this paper. The definition of simple graph grammars is given in the second section. In the third section it is proved that the system of simple graph grammars is complete. The final section gives a generalization of the system of simple graph grammars.