Journal of Logic and Computation vol:23 issue:4 pages:799-814
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 paper we take a further step in this direction and work within the framework of node label controlled (NLC) graph grammars. Speciﬁcally, we characterize, given a set of disjoint and isomorphic subgraphs of a graph G, whether or not there is a NLC graph grammar rule which can generate these subgraphs to obtain
G. This generalizes previous results by assuming that the set of isomorphic subgraphs is disjoint instead of non-touching. This leads naturally to consider the more involved ''non-conﬂuent'' graph grammar rules.