---
title: "Mapping Between English Strings and Reentrant Semantic Graphs — paper by Braune et al. (2014)"
description: "The paper asks whether graph transduction formalisms with good computational properties can concisely describe how… 22 references, cited by 3 papers here."
authors: ["Fabienne Braune", "Daniel Bauer", "Kevin Knight"]
year: 2014
venue: "Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'14)"
source: "https://aclanthology.org/L14-1061/"
licence: "CC BY-NC 4.0 (ELRA, LREC proceedings)"
licence_url: "https://creativecommons.org/licenses/by-nc/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/braune-2014-mapping-between-english-strings-reentrant/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/braune-2014-mapping-between-english-strings-reentrant/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2014](https://md.research.elamur.ai/free/en/papers/2014/page/3/) / Mapping Between English Strings and Reentrant Semantic Graphs

# Mapping Between English Strings and Reentrant Semantic Graphs

**Authors:** Fabienne Braune, [Daniel Bauer](https://md.research.elamur.ai/free/en/authors/daniel-bauer/) and [Kevin Knight](https://md.research.elamur.ai/free/en/authors/kevin-knight/) · **Year:** 2014 · **Venue:** [Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'14)](https://md.research.elamur.ai/free/en/venues/lrec/) ([LREC 2014](https://md.research.elamur.ai/free/en/venues/lrec/2014/)) · **Publisher:** [European Language Resources Association (ELRA)](https://md.research.elamur.ai/free/en/publishers/european-language-resources-association-elra/) · **Licence:** [CC BY-NC 4.0 (ELRA, LREC proceedings)](https://creativecommons.org/licenses/by-nc/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/L14-1061/) · [PDF](https://aclanthology.org/L14-1061.pdf) · [OpenAlex](https://openalex.org/W2250668036)

**Citations:** 11 citations (OpenAlex, 2026-10-14) · 3 in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper asks whether graph transduction formalisms with good computational properties can concisely describe how English expresses reentrancy in semantic graphs, where one entity fills several roles. The authors built a synthetic microworld corpus: one program enumerates every graph over two predicates (WANT, BELIEVE), two entities (BOY, GIRL) and two relations (ARG0, ARG1), starting from the smallest. A second, non-declarative program produces up to ten English sentences per graph. These sentences use pronouns, zero pronouns, reflexives, passives, control and nominalizations.

Expert-written grammars were built in three setups: a single SHRG, a DAG-to-tree transducer followed by a tree-to-string transducer, and a longer cascade that handles verb forms and pronouns in separate stages. Each was run in both directions. Generation was scored with BLEU, understanding with Smatch, and conciseness by rule count and size in bytes.

The cascade needed the fewest rules and D2T the most. Generation reached full coverage, but understanding coverage stayed low. The authors conclude that none of the formalisms handles the data elegantly. They release the corpus as a benchmark for better formalisms.

## Key points
- The dataset has 10,000 semantic graphs with up to 10 English realizations each, 98,818 strings in total. It is available at amr.isi.edu (boygirl.tgz).
- Each graph contains at most one entity of each gender, and predicates take zero to two arguments. Entities can be shared across many predicate instances, which creates long coreference chains and long-distance reflexives.
- Three solutions were compared: SHRG (Jones et al., 2012), D2T + LNTs, and D2T + two xLNT + LNTs. All were tested with existing generic automata toolkits.
- Generation was evaluated with BLEU against the references and understanding with Smatch. Both directions also report coverage, rule count and bytes.
- The cascade was the most compact. D2T needed the most rules because of long coreference chains with varied pronoun forms. SHRG fell in between, since agreement has to be encoded in its nonterminals, and it was slightly less accurate in generation.

## Interesting ideas
- Generating a benchmark by exhaustively enumerating meaning structures in a tiny closed domain, smallest first, gives unlimited, fully controlled data aimed at one hard phenomenon (reentrancy).
- In the cascade, the first stage emits abstract entity placeholders. Later small passes choose verb inflection and pronoun form, which avoids a rule explosion from combining structure with surface variants.
- The same grammar is required to work in both directions, so it cannot simply overgenerate. Understanding and generation are scored on the same data with Smatch and BLEU.
- Conciseness, measured as rule count and bytes, is treated as a first-class metric next to accuracy, because a formalism that needs exploding rule sets fits the language poorly.
- In SHRG, hyperedges keep handles to referents introduced earlier, so later fragments can attach to them. The graph's reentrant nodes are built up incrementally rather than all at once.

## For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

- **I1** (learn): A similar microworld of frames could produce graph–sentence pairs to stress-test coreference and control, acting as a clean negative-control set.
- **I2** (back): Generation from the meaning graph could first linearize with entity IDs, then run separate explainable passes for verb morphology and pronoun/reflexive choice.
- **I3** (back): The text → graph → text compressor could report both directions on one corpus to expose asymmetries between parsing and generation.
- **I4** (learn): Self-induced repair rules could be tracked by count and size alongside accuracy, flagging phenomena where rules multiply instead of generalizing.
- **I5** (world): When building the world of a text, open entity handles could be carried through the derivation so later clauses (zero subjects in control, reflexives) bind to them explicitly.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Columbia University](https://md.research.elamur.ai/free/en/universities/columbia-university/) — University, New York, United States · 149 works · 48,852 citations
- [University of Southern California](https://md.research.elamur.ai/free/en/universities/university-of-southern-california/) — University, Los Angeles, United States · 104 works · 33,876 citations
- [University of Stuttgart](https://md.research.elamur.ai/free/en/universities/university-of-stuttgart/) — University, Stuttgart, Germany · 75 works · 46,113 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

🧭 Topics (1): [English](https://md.research.elamur.ai/free/en/topics/english/) · 1,373 works

## Cite

Cite as: Fabienne Braune, Daniel Bauer and Kevin Knight. 2014. Mapping Between English Strings and Reentrant Semantic Graphs. Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'14).

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{braune2014mapping,
  title = {{Mapping Between English Strings and Reentrant Semantic Graphs}},
  author = {Fabienne Braune, Daniel Bauer and Kevin Knight},
  booktitle = {Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC'14)},
  year = {2014},
  doi = {10.63317/44jchxktu3ji},
  url = {https://doi.org/10.63317/44jchxktu3ji}
}
```

- [← previous Towards Cross-Domain PDTB-Style Discourse Parsing](https://md.research.elamur.ai/free/en/papers/stepanov-2014-cross-domain-pdtb-style-discourse/)
- [next → Anaphora Models and Reordering for Phrase-Based SMT](https://md.research.elamur.ai/free/en/papers/hardmeier-2014-anaphora-models-reordering-phrase-based/)
- [↑ back to papers of 2014](https://md.research.elamur.ai/free/en/papers/2014/page/3/)

## References

22 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Banarescu, L., Bonial, C., Cai, S., Georgescu, M., Griffitt, K., Hermjakob, U., Knight, K., Koehn, P., Palmer, M., and Schneider, N. (2013). Abstract meaning representation for sembanking. In Proc. ACL Linguistic Annotation Workshop. [our card](https://md.research.elamur.ai/free/en/papers/banarescu-2013-abstract-meaning-representation-sembanking/)
2. Basile, V., Bos, J., Evang, K., and Venhuizen, N. (2012). Developing a large semantically annotated corpus. In Proc. LREC. [our card](https://md.research.elamur.ai/free/en/papers/basile-2012-developing-large-semantically-annotated-corpus/)
3. Bohnet, B. and Wanner, L. (2001). On using a parallel graph rewriting formalism in generation. In Proc. EWNLG Workshop. [find](https://scholar.google.com/scholar?q=Bohnet%2C+B%2E+and+Wanner%2C+L%2E+%282001%29%2E+On+using+a+parallel+graph+rewriting+formalism+in+generation%2E+In+Proc%2E+EWNLG+Workshop%2E)
4. Cai, S. and Knight, K. (2013). Smatch: an evaluation metric for semantic feature structures. In Proc. ACL. [find](https://scholar.google.com/scholar?q=Cai%2C+S%2E+and+Knight%2C+K%2E+%282013%29%2E+Smatch%3A+an+evaluation+metric+for+semantic+feature+structures%2E+In+Proc%2E+ACL%2E)
5. Chiang, D., Andreas, J., Bauer, D., Hermann, K. M., Jones, B., and Knight, K. (2013). Parsing graphs with hyperedge replacement grammars. In Proc. ACL. [find](https://scholar.google.com/scholar?q=Chiang%2C+D%2E%2C+Andreas%2C+J%2E%2C+Bauer%2C+D%2E%2C+Hermann%2C+K%2E+M%2E%2C+Jones%2C+B%2E%2C+and+Knight%2C+K%2E+%282013%29%2E+Parsing+graphs+with+hyperedge+replacement+grammars%2E+In+Proc%2E+ACL%2E)
6. Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. (1997). Tree automata techniques and applications. Available on www.grappa.univ-lille3.fr/tata. release October, 1st 2002. [find](https://scholar.google.com/scholar?q=Comon%2C+H%2E%2C+Dauchet%2C+M%2E%2C+Gilleron%2C+R%2E%2C+Jacquemard%2C+F%2E%2C+Lugiez%2C+D%2E%2C+Tison%2C+S%2E%2C+and+Tommasi%2C+M%2E+%281997%29%2E+Tree+automata+techniques+and+applications%2E+Available+on+www%2Egrappa%2Euniv%2Dlille3%2Efr%2Ftata%2E+release+Oct)
7. Jones, B., Andreas*, J., Bauer*, D., Hermann*, K. M., and Knight, K. (2012). Semantics-based machine translation with hyperedge replacement grammars. In Proc. COL-ING. *first authorship shared. [our card](https://md.research.elamur.ai/free/en/papers/jones-2012-semantics-based-machine-translation-hyperedge/)
8. Joshi, A. and Schabes, Y. (1997). Tree-adjoining grammars. In Rozenberg, G. and Salomaa, A., editors, Handbook of Formal Languages (Vol. 3). Springer. Proposed Solution # of rules # of bytes NLG coverage SHRG D2T Cascade 242 361 105 18035 21533 3843 100 100 100 Figure 11: Results of three automata solutions applied to our graph/string data. [↗](https://doi.org/10.1007/978-3-642-59126-6_2)
9. Kamimura, T. and Slutzki, G. (1982). Transductions of dags and trees. Theory of Computing Systems, 15(1). [↗](https://doi.org/10.1007/bf01786981)
10. King, T. Holloway, Crouch, R., Riezler, S., Dalrymple, M., and Kaplan, R.M. (2003). The PARC 700 dependency bank. In Proc. LINC Workshop. [find](https://scholar.google.com/scholar?q=King%2C+T%2E+Holloway%2C+Crouch%2C+R%2E%2C+Riezler%2C+S%2E%2C+Dalrymple%2C+M%2E%2C+and+Kaplan%2C+R%2EM%2E+%282003%29%2E+The+PARC+700+dependency+bank%2E+In+Proc%2E+LINC+Workshop%2E)
11. Knight, K. and Al-Onaizan, Y. (1998). Translation with finite-state devices. In Proc. AMTA. [find](https://scholar.google.com/scholar?q=Knight%2C+K%2E+and+Al%2DOnaizan%2C+Y%2E+%281998%29%2E+Translation+with+finite%2Dstate+devices%2E+In+Proc%2E+AMTA%2E)
12. Knight, K. and Graehl, J. (1998). Machine transliteration. Computational Linguistics, 24(4). [our card](https://md.research.elamur.ai/free/en/papers/knight-1998-machine-transliteration/)
13. Knight, K. and Graehl, J. (2005). An overview of probabilistic tree transducers for natural language processing. In Proc. CICLING. [find](https://scholar.google.com/scholar?q=Knight%2C+K%2E+and+Graehl%2C+J%2E+%282005%29%2E+An+overview+of+probabilistic+tree+transducers+for+natural+language+processing%2E+In+Proc%2E+CICLING%2E)
14. Kroeger, Paul. (2004). Analyzing Syntax : A Lexical-Functional Approach. Cambridge University Press. [find](https://scholar.google.com/scholar?q=Kroeger%2C+Paul%2E+%282004%29%2E+Analyzing+Syntax+%3A+A+Lexical%2DFunctional+Approach%2E+Cambridge+University+Press%2E)
15. Maletti, A., Graehl, J., Hopkins, M., and Knight, K. (2008). The power of extended top-down tree transducers. SIAM J. Computing, 39(2). [↗](https://doi.org/10.1137/070699160)
16. May, J. and Knight, K. (2006). Tiburon: A weighted tree automata toolkit. In Proc. CIAA. [find](https://scholar.google.com/scholar?q=May%2C+J%2E+and+Knight%2C+K%2E+%282006%29%2E+Tiburon%3A+A+weighted+tree+automata+toolkit%2E+In+Proc%2E+CIAA%2E)
17. Moore, R. C. (1989). Unification-based semantic interpretation. In Proc. ACL. [find](https://scholar.google.com/scholar?q=Moore%2C+R%2E+C%2E+%281989%29%2E+Unification%2Dbased+semantic+interpretation%2E+In+Proc%2E+ACL%2E)
18. Oepen, S., Toutanova, K., Shieber, S., Manning, C., Flickinger, D., and Brants, T. (2002). The LinGO redwoods treebank : Motivation and preliminary applications. In Proc COLING. [our card](https://md.research.elamur.ai/free/en/papers/oepen-2002-lingo-redwoods-treebank-motivation-preliminary/)
19. Papineni, K., Roukos, S., Ward, T., and Zhu, W. (2002). Bleu: a method for automatic evaluation of machine translation. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
20. Pereira, F., Riley, M., and Sproat, R. (1994). Weighted rational transductions and their application to human language processing. In Proc. HLT. [find](https://scholar.google.com/scholar?q=Pereira%2C+F%2E%2C+Riley%2C+M%2E%2C+and+Sproat%2C+R%2E+%281994%29%2E+Weighted+rational+transductions+and+their+application+to+human+language+processing%2E+In+Proc%2E+HLT%2E)
21. Pollard, Carl J. and Sag, Ivan A. (1994). Head-Driven Phrase Structure Grammar. University of Chicago Press. [find](https://scholar.google.com/scholar?q=Pollard%2C+Carl+J%2E+and+Sag%2C+Ivan+A%2E+%281994%29%2E+Head%2DDriven+Phrase+Structure+Grammar%2E+University+of+Chicago+Press%2E)
22. Quernheim, D. and Knight, K. (2012). DAGGER: a toolkit for automtata on directed acyclic graphs. In Proc. FSMNLP. NLG accuracy (Bleu) 88.13 90.13 90.13 NLU coverage NLU accuracy (Smatch) 90 83 79 4.9 3.9 4.3 [find](https://scholar.google.com/scholar?q=Quernheim%2C+D%2E+and+Knight%2C+K%2E+%282012%29%2E+DAGGER%3A+a+toolkit+for+automtata+on+directed+acyclic+graphs%2E+In+Proc%2E+FSMNLP%2E+NLG+accuracy+%28Bleu%29+88%2E13+90%2E13+90%2E13+NLU+coverage+NLU+accuracy+%28Smatch%29+90+83+79+4%2E9+)

*Updated 24 October 2026*