Parsing graphs with hyperedge replacement grammars

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

Parsing graphs with hyperedge replacement grammars

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

Department of Computing

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

33 Citations (Scopus)

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

Access to Document

http://www.aclweb.org/anthology/P13-1091

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

Cite this

@inproceedings{17b9081f663b45cba2b83e621378c5ff,

title = "Parsing graphs with hyperedge replacement grammars",

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.",

author = "David Chiang and Hermann, {Karl Moritz} and Jacob Andreas and Bevan Jones and Daniel Bauer and Kevin Knight",

year = "2013",

language = "English",

isbn = "9781937284503",

pages = "924--932",

booktitle = "Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics",

}

Chiang, D, Hermann, KM, Andreas, J, Jones, B, Bauer, D & Knight, K 2013, Parsing graphs with hyperedge replacement grammars. in Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics: ACL 2013 : 4-9 August, Sofia, Bulgaria. Association for Computational Linguistics, Stroudsburg, PA, pp. 924-932, Annual Meeting of the Association for Computational Linguistics (51st : 2013), Sofia, Bulgaria, 4/08/13.

Parsing graphs with hyperedge replacement grammars. / Chiang, David; Hermann, Karl Moritz; Andreas, Jacob; Jones, Bevan; Bauer, Daniel; Knight, Kevin.

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics: ACL 2013 : 4-9 August, Sofia, Bulgaria. Stroudsburg, PA : Association for Computational Linguistics, 2013. p. 924-932.

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

TY - GEN

T1 - Parsing graphs with hyperedge replacement grammars

AU - Chiang, David

AU - Hermann, Karl Moritz

AU - Andreas, Jacob

AU - Jones, Bevan

AU - Bauer, Daniel

AU - Knight, Kevin

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

M3 - Conference proceeding contribution

SN - 9781937284503

SP - 924

EP - 932

BT - Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics

PB - Association for Computational Linguistics

CY - Stroudsburg, PA

ER -