Skip to main navigation Skip to search Skip to main content

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 proceeding › Conference proceeding contribution › peer-review

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 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
Pages924-932
Number of pages9
ISBN (Print)9781937284503
Publication statusPublished - 2013
EventAnnual Meeting of the Association for Computational Linguistics (51st : 2013) - Sofia, Bulgaria
Duration: 4 Aug 2013 → 9 Aug 2013

Conference

ConferenceAnnual Meeting of the Association for Computational Linguistics (51st : 2013)
CitySofia, Bulgaria
Period4/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