Between a Rock and a Hard Place: Parsing for Hyperege Replacement DAG Grammars
2016 (English)In: Proc. 10th International Conference on Language and Automata Theory and Applications (LATA 2016) / [ed] A.H. Dediu, J. Janoušek, C. Martín-Vide, and B. Truthe, Springer Publishing Company, 2016, Vol. 9618, 521-532 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
Springer Publishing Company, 2016. Vol. 9618, 521-532 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 9618
Graph grammar, Hyperedge replacement, Abstract meaning representation, DAG grammar, Uniform membership problem, Parsing
IdentifiersURN: urn:nbn:se:umu:diva-111984DOI: 10.1007/978-3-319-30000-9_40ISI: 000378745100045ISBN: 978-3-319-30000-9ISBN: 978-3-319-29999-0OAI: oai:DiVA.org:umu-111984DiVA: diva2:874860
10th International Conference on Language and Automata Theory and Applications (LATA 2016), Prague, Czech Republic, March 14-18, 2016