Edge-label controlled graph grammars

摘要

We introduce a graph-grammar model based on edge-replacement, where both the rewriting and the embedding mechanisms are controlled by edge labels. The general power of this model is established—it turns out to have the complete power of recursive enumerability (in a sense to be made precise in the paper). In order to understand where this power originates, we identify three basic features of the embedding mechanism and examine how restrictions on these features affect the generative power. In particular, by imposing restrictions on all three features simultaneously, we obtain a graph-grammar model that was previously introduced by Kreowski and Habel.