On the inference of non-confluent NLC graph grammars

Abstract

Grammar inference deals with determining (preferably simple) models/grammars consistent with a set of observations. There is a large body of research on grammar inference within the theory of formal languages. However, there is surprisingly little known on grammar inference for graph grammars. In this article, we take a further step in this direction and work within the framework of node label controlled (NLC) graph grammars. Specifically, given a graph G and a set S of disjoint and isomorphic subgraphs of G, we characterize whether or not there is a graph grammar consisting of one production such that G may be derived from G(0), the graph obtained from G by 'contraction' of each subgraph in S to a node labelled by N. This generalizes a previous result that assumes boundary NLC graph grammars, and leads one to consider the more involved 'non-confluent' graph grammar rules.