Skip to content
Show report in:

UMINF 15.13

Between a Rock and a Hard Place - Parsing for Hyperedge Replacement DAG Grammars

We study the uniform membership problem for hyperedge-replacement grammars that generate directed acyclic graphs. The study of this type of language is motivated by applications in natural language processing. Our major result is a low-degree polynomial-time algorithm that solves the uniform membership problem for a restricted type of such grammars. We motivate the necessity of the restrictions by two different NP-completeness results.


No keywords specified


Henrik Björklund , Frank Drewes and Petter Ericson

Back Edit this report
Entry responsible: Petter Ericson

Page Responsible: Frank Drewes