A system of graph grammars which generates all recursively enumerable sets of labelled graphs

摘要

The aim of this paper is to prove that the system of simple graph grammars (Einfache Graph-Grammatiklen) in [1] is complete. A graph grammar is generakization 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. ...