Handle NLC grammars and R. E. languages

摘要

A graph grammar is a mechanism for generating sets of graphs (called graph languages). This paper examines the generating power of a simple extension of the well studied node-label controlled graph grammars. We show that the extension, called handle NLC grammars, gives the ability to generate any recursively enumerable graph language. The proof proceeds in three steps. First we show how a handle NLC grammar can simulate a phrase-structure string grammar, where the strings that the phrase-structure grammar works on are considered to be graphs of a special form. Then we demonstrate a way of encoding graphs as strings. The final step shows how a handle NLC grammar can convert a string encoding of a graph into the graph itself.