Parsing graphs with hyperedge replacement grammars

David Chiang, Karl Moritz Hermann, Jacob Andreas, Bevan Jones, Daniel Bauer, Kevin Knight

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

33 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the 51st Annual Meeting of the Association for Computational Linguistics
Subtitle of host publicationACL 2013 : 4-9 August, Sofia, Bulgaria
Place of PublicationStroudsburg, PA
PublisherAssociation for Computational Linguistics
Number of pages9
ISBN (Print)9781937284503
Publication statusPublished - 2013
EventAnnual Meeting of the Association for Computational Linguistics (51st : 2013) - Sofia, Bulgaria
Duration: 4 Aug 20139 Aug 2013


ConferenceAnnual Meeting of the Association for Computational Linguistics (51st : 2013)
CitySofia, Bulgaria

Fingerprint Dive into the research topics of 'Parsing graphs with hyperedge replacement grammars'. Together they form a unique fingerprint.

Cite this