Designing and Learning Substitutable Plane Graph Grammars

Though graph grammars have been widely investigated for 40 years, few learning results exist for them. The main reasons come from complexity issues that are inherent when graphs, and a fortiori graph grammars, are considered. The picture is however different if one considers drawings of graphs, rat her than the graphs themselves. For instance, it has recently been proved that the isomorphism and pattern searching problems could be solved in polynomial time for plane graphs, that is, planar embeddings of planar graphs. In this paper, we introduce the Plane Graph Grammars (PGG) and detail how they differ to usual graph grammar formalism’s while at the same time they share important properties with string context-free grammars. In particular, though exponential in the general case, we provide an appropriate restriction on languages that allows the parsing of a graph with a given PGG in polynomial time. We demonstrate that PGG are well-shaped for learning: we show how recent results on string grammars can be extended to PGG by providing a learning algorithm that identifies in the limit the class of substitutable plane graph languages. Our algorithm runs in polynomial time assuming the same restriction used for polynomial parsing, and the amount of data needed for convergence is comparable to the one required in the case of strings.