Skip to content
printicon
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.

Keywords

No keywords specified

Authors

Henrik Björklund , Frank Drewes and Petter Ericson

Back Edit this report
Entry responsible: Petter Ericson

Page Responsible: Frank Drewes
2022-09-30