Abstract
Hyperedge replacement grammar (HRG) is a formalism for generating and transforming graphs that has potential applications in natural language understanding and generation. A recognition algorithm due to Lautemann is known to be polynomial-time for graphs that are connected and of bounded degree. We present a more precise characterization of the algorithm's complexity, an optimization analogous to binarization of contextfree grammars, and some important implementation details, resulting in an algorithm that is practical for natural-language applications. The algorithm is part of Bolinas, a new software toolkit for HRG processing.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics |
| Subtitle of host publication | ACL 2013 : 4-9 August, Sofia, Bulgaria |
| Place of Publication | Stroudsburg, PA |
| Publisher | Association for Computational Linguistics |
| Pages | 924-932 |
| Number of pages | 9 |
| ISBN (Print) | 9781937284503 |
| Publication status | Published - 2013 |
| Event | Annual Meeting of the Association for Computational Linguistics (51st : 2013) - Sofia, Bulgaria Duration: 4 Aug 2013 → 9 Aug 2013 |
Conference
| Conference | Annual Meeting of the Association for Computational Linguistics (51st : 2013) |
|---|---|
| City | Sofia, Bulgaria |
| Period | 4/08/13 → 9/08/13 |
Fingerprint
Dive into the research topics of 'Parsing graphs with hyperedge replacement grammars'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver