Name
Title | ||
|---|---|---|
Between a Rock and a Hard Place - Uniform Parsing for Hyperedge Replacement DAG Grammars. |
Abstract | ||
|---|---|---|
Motivated by applications in natural language processing, we study the uniform membership problem for hyperedge-replacement grammars that generate directed acyclic graphs. 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-30000-9_40 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Graph grammar,Hyperedge replacement,Abstract meaning representation,DAG grammar,Uniform membership problem,Parsing | Rule-based machine translation,Programming language,Computer science,Directed acyclic graph,Parsing,Membership problem | Conference |
Volume | ISSN | Citations |
9618 | 0302-9743 | 5 |
PageRank | References | Authors |
0.43 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henrik Björklund | 1 | 311 | 20.41 |
| Frank Drewes | 2 | 26 | 6.10 |
| Petter Ericson | 3 | 7 | 2.15 |