Modeling Graph Languages with Grammars Extracted via Tree Decompositions

Bevan K. Jones, Mark Johnson, Sharon Goldwater

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

Abstract / Description of output

Work on probabilistic models of natural language tends to focus on strings and trees, but there is increasing interest in more general graph-shaped structures since they seem to be better suited for representing natural language semantics, ontologies, or other varieties of knowledge structures. However, while there are relatively simple approaches to defining generative models over strings and trees, it has proven more challenging for more general graphs. This paper describes a natural generalization of the n-gram to graphs, making use of Hyperedge Replacement Grammars to define generative models of graph languages.
Original languageEnglish
Title of host publicationProceedings of the 11th Conference on Finite-State Methods and Natural Language Processing
Number of pages9
Publication statusPublished - 2013


Dive into the research topics of 'Modeling Graph Languages with Grammars Extracted via Tree Decompositions'. Together they form a unique fingerprint.

Cite this