Uniform parsing for hyperedge replacement grammars (Q2656168)

The contribution discusses polynomial-time uniform parsing for certain hyperedge-replacement grammars. A hyperedge in a graph is a special edge that has one source node, but potentially many target nodes. A hyperedge-replacement grammar specifies in its productions how an individual hyperedge can be replaced by a graph that is connected to the source node and target nodes of the original hyperedge. No other connections between the original graph, also called host graph, and the replacement graph is possible. The uniform parsing problem takes a hyperedge-replacement grammar \(\mathcal G\) as well as a graph \(G\) as input and asks whether the given grammar \(\mathcal G\) can generate the graph \(G\). It is well known that such hyperedge-replacement grammars can generate NP-complete languages, so a general polynomial-time uniform parsing algorithm is unlikely. However, for a restricted but relevant class of hyperedge-replacement grammars the contribution presents such a polynomial-time uniform parsing algorithm (for some low-degree polynomial). The approach chosen by the authors to retain polynomial-time uniform parsing essentially enforces that applications of the mentioned replacement step can be undone deterministically. Given the resulting graph and the production that was applied and the location where it was applied, the replacement graph is completely removed and the original hyperedge that was replaced can be reintroduced with the correct source and target connections. This requirement is achieved by two separate conditions. The first condition is reentrancy preservation, which allows to identify the nodes that belong to the source and target nodes of the original hyperedge. The second condition is order preservation, which allows to identify the order of the target nodes. It is demonstrated that these two conditions can be effectively checked and allow for hyperedge-replacement grammars that are relevant in natural language processing. The obtained uniform parsing algorithm is similar to the classical CYK-parsing algorithm for context-free grammars. The paper is extremely well written and contains many explanations and examples. Illustrations are generously provided. Some experience with graph rewriting on behalf of the reader is certainly helpful but absolutely not required. Anyone with some background in formal language theory should be able to fully appreciate the contribution.