[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/hennig-2017-dependency-tree-transformation-tree-transducers/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / Dependency Tree Transformation with Tree Transducers

# Dependency Tree Transformation with Tree Transducers

**Authors:** Felix Hennig, Arne Köhn · **Year:** 2017 · **Venue:** Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017) **Link:** [aclanthology.org/W17-0407](https://aclanthology.org/W17-0407/) · **Licence:** [CC BY 4.0](https://creativecommons.org/licenses/by/4.0/)

[**7** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/hennig-2017-dependency-tree-transformation-tree-transducers/) of the 140673 papers whose bibliographies we read[Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017)](https://aclanthology.org/volumes/W17-04/)[licence](https://creativecommons.org/licenses/by/4.0/)

- [Publisher's page](https://aclanthology.org/W17-0407/)
- [PDF](https://aclanthology.org/W17-0407.pdf)

**Authors (2)**

1. Felix Hennig
2. Arne Köhn

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## What it is about

The paper addresses converting treebanks from one dependency schema to another, for example from a language-specific schema to Universal Dependencies, or from one UD version to the next. The authors apply top-down tree transducers to dependency trees. A rule matches a node with its local context, meaning its label, its part-of-speech tag and its children, and rewrites the subtree. Because each rule leaves a well-formed tree, every step is a valid tree, which earlier rule-based converters did not guarantee. The rules are extracted from a small set of hand-converted sentences. With a rule set built from only 45 manually converted sentences of the Hamburg Dependency Treebank, the rules reach coverage and precision above 90 per cent on the conversion task. The example shown is the conversion of a spelled-out number into its digit form, which needs a rule that moves the words under one head.

## Ideas

- I1. Use the transducer's rule form for the source-side trees of Mova: Hebrew trees from MACULA and any treebank that is not in the current UD version need a conversion step. Write each change as a local rule (label, tag, and children) and count how often each rule applies, so each conversion can be checked by hand.
- I2. Well-formedness as a check: the paper's rule guarantees a valid tree after each step. Add the same check to `tools/roundtrip` after each stage of the reader, and count the verses where a stage would produce an invalid tree.
- I3. Learn rules from a few verses: the paper extracts rules from a small manual set, then measures coverage and precision on the rest. The translator's Hebrew reader (`tools/translate/src/hebrew.rs`) can use the same measure for its tree-to-meta rules, with a held-out set of verses.
- I4. Report precision and coverage per rule, not only per corpus: a rule that is correct on 90 per cent of its matches but applies to few nodes should be listed separately, so a bad rule is seen before it reaches the residual.

## For Mova

The code is `tools/macula` (MACULA trees, UD form) and `tools/roundtrip` (the tree checks). The approach is rule-based and counted, which fits Mova's mechanics. The paper does not use any learned model, so nothing needs to be borrowed beyond the rule form and the measures.

Topics: [Dependency parsing](https://md.mova.elamur.ai/free/en/docs/papers/topics/dependency-parsing/) · [Treebanks](https://md.mova.elamur.ai/free/en/docs/papers/topics/treebanks/) · [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/topics/machine-translation/)

## Cite

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

```
@inproceedings{hennig2017dependency,
  title = {{Dependency Tree Transformation with Tree Transducers}},
  author = {Hennig, Felix and Köhn, Arne},
  booktitle = {Proceedings of the NoDaLiDa 2017 Workshop on Universal Dependencies (UDW 2017)},
  year = {2017},
  url = {https://aclanthology.org/W17-0407/}
}
```

- [← previous Time to eat peaches: language-specific information in interlingua](https://md.mova.elamur.ai/free/en/docs/papers/helmreich-1997-time-eat-peaches-language-specific/)
- [next → Comparison by Conversion: Reverse-Engineering UCCA from Syntax and Lexical Semantics](https://md.mova.elamur.ai/free/en/docs/papers/hershcovich-2020-comparison-conversion-reverse-engineering-ucca/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## References

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

1. Hélène Mazo, Asunción Moreno, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Tenth International Conference on Language Resources and Evaluation LREC 2016, Portorož, Slovenia, May 23-28, 2016. European Language Resources Association (ELRA). [find](https://scholar.google.com/scholar?q=He%CC%81le%CC%80ne+Mazo%2C+Asuncio%CC%81n+Moreno%2C+Jan+Odijk%2C+and+Stelios+Piperidis%2C+editors%2C+Proceedings+of+the+Tenth+International+Conference+on+Language+Resources+and+Evaluation+LREC+2016%2C+Portoroz%CC%8C%2C+Slovenia%2C+May+2)
2. Lars Ahrenberg. 2015. Converting an english-swedish parallel treebank to universal dependencies. In Proceedings of the Third International Conference on Dependency Linguistics (Depling 2015), pages 10– 19, Uppsala, Sweden, August. Uppsala University, Uppsala, Sweden. [find](https://scholar.google.com/scholar?q=Lars+Ahrenberg%2E+2015%2E+Converting+an+english%2Dswedish+parallel+treebank+to+universal+dependencies%2E+In+Proceedings+of+the+Third+International+Conference+on+Dependency+Linguistics+%28Depling+2015%29%2C+pages+10) [our card](https://md.mova.elamur.ai/free/en/docs/papers/ud-2015-ahrenberg-converting-english-swedish-parallel-treebank/)
3. Sampo Pyysalo, Jenna Kanerva, Anna Missilä, Veronika Laippala, and Filip Ginter. 2015. Universal dependencies for finnish. In Proceedings of the 20th Nordic Conference of Computational Linguistics (NODALIDA 2015), pages 163–172, Vilnius, Lithuania, May. Linköping University Electronic Press, Sweden. [find](https://scholar.google.com/scholar?q=Sampo+Pyysalo%2C+Jenna+Kanerva%2C+Anna+Missila%CC%88%2C+Veronika+Laippala%2C+and+Filip+Ginter%2E+2015%2E+Universal+dependencies+for+finnish%2E+In+Proceedings+of+the+20th+Nordic+Conference+of+Computational+Linguistics+%28N)
4. Kilian A. Foth, Arne Köhn, Niels Beuck, and Wolfgang Menzel. 2014. Because size does matter: The Hamburg Dependency Treebank. In Proceedings of the Language Resources and Evaluation Conference 2014. LREC, European Language Resources Association (ELRA). [find](https://scholar.google.com/scholar?q=Kilian+A%2E+Foth%2C+Arne+Ko%CC%88hn%2C+Niels+Beuck%2C+and+Wolfgang+Menzel%2E+2014%2E+Because+size+does+matter%3A+The+Hamburg+Dependency+Treebank%2E+In+Proceedings+of+the+Language+Resources+and+Evaluation+Conference+2014%2E+)
5. Corentin Ribeyre, Djamé Seddah, and Éric Villemonte de la Clergerie. 2012. A linguistically-motivated 2-stage tree to graph transformation. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11), pages 214–222, Paris, France, September. [find](https://scholar.google.com/scholar?q=Corentin+Ribeyre%2C+Djame%CC%81+Seddah%2C+and+E%CC%81ric+Villemonte+de+la+Clergerie%2E+2012%2E+A+linguistically%2Dmotivated+2%2Dstage+tree+to+graph+transformation%2E+In+Proceedings+of+the+11th+International+Workshop+on+Tree+)
6. Anders Johannsen, Héctor Martı́nez Alonso, and Barbara Plank. 2015. Universal dependencies for danish. In Markus Dickinson, Erhard Hinrichs, Agnieszka Patejuk, and Adam Przepiórkowski, editors, Proceedings of the Fourteenth International Workshop on Treebanks and Linguistic Theories (TLT14), pages 157–167, Warsaw, Poland. [find](https://scholar.google.com/scholar?q=Anders+Johannsen%2C+He%CC%81ctor+Mart%C4%B1%CC%81nez+Alonso%2C+and+Barbara+Plank%2E+2015%2E+Universal+dependencies+for+danish%2E+In+Markus+Dickinson%2C+Erhard+Hinrichs%2C+Agnieszka+Patejuk%2C+and+Adam+Przepio%CC%81rkowski%2C+editors%2C+Proc)
7. Juhi Tandon, Himani Chaudhry, Riyaz Ahmad Bhat, and Dipti Misra Sharma. 2016. Conversion from paninian karakas to universal dependencies for hindi dependency treebank. In Katrin Tomanek and Annemarie Friedrich, editors, Proceedings of the 10th Linguistic Annotation Workshop held in conjunction with ACL 2016, LAW@ACL 2016, August 11, 2016, Berlin, Germany. The Association for Computer Linguistics. [find](https://scholar.google.com/scholar?q=Juhi+Tandon%2C+Himani+Chaudhry%2C+Riyaz+Ahmad+Bhat%2C+and+Dipti+Misra+Sharma%2E+2016%2E+Conversion+from+paninian+karakas+to+universal+dependencies+for+hindi+dependency+treebank%2E+In+Katrin+Tomanek+and+Annemarie+)
8. Bevan Jones, Mark Johnson, and Sharon Goldwater. 2011. Formalizing semantic parsing with tree transducers. In Proceedings of the Australasian Language Technology Association Workshop 2011, pages 19–28, Canberra, Australia, December. [find](https://scholar.google.com/scholar?q=Bevan+Jones%2C+Mark+Johnson%2C+and+Sharon+Goldwater%2E+2011%2E+Formalizing+semantic+parsing+with+tree+transducers%2E+In+Proceedings+of+the+Australasian+Language+Technology+Association+Workshop+2011%2C+pages+19%E2%80%9328)
9. Andreas Maletti. 2010. Survey: Tree transducers in machine translation. In Henning Bordihn, Rudolf Freund, Thomas Hinze, Markus Holzer, Martin Kutrib, and Friedrich Otto, editors, Proc. 2nd Int. Workshop Non-Classical Models of Automata and Applications, volume 263 of books@ ocg. at , pages 11–32. Österreichische Computer Gesellschaft. [find](https://scholar.google.com/scholar?q=Andreas+Maletti%2E+2010%2E+Survey%3A+Tree+transducers+in+machine+translation%2E+In+Henning+Bordihn%2C+Rudolf+Freund%2C+Thomas+Hinze%2C+Markus+Holzer%2C+Martin+Kutrib%2C+and+Friedrich+Otto%2C+editors%2C+Proc%2E+2nd+Int%2E+Works)
10. James W. Thatcher. 1970. Generalized sequential machine maps. Journal of Computer and System Sciences, 4(4):339–367. [find](https://scholar.google.com/scholar?q=James+W%2E+Thatcher%2E+1970%2E+Generalized+sequential+machine+maps%2E+Journal+of+Computer+and+System+Sciences%2C+4%284%29%3A339%E2%80%93367%2E)
11. Francis M. Tyers and Mariya Sheyanova. 2017. Annotation schemes in north sámi dependency parsing. In Proceedings of the Third Workshop on Computational Linguistics for Uralic Languages, pages 66– 75, St. Petersburg, Russia, January. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Francis+M%2E+Tyers+and+Mariya+Sheyanova%2E+2017%2E+Annotation+schemes+in+north+sa%CC%81mi+dependency+parsing%2E+In+Proceedings+of+the+Third+Workshop+on+Computational+Linguistics+for+Uralic+Languages%2C+pages+66%E2%80%93+75%2C)
12. Ryan McDonald, Joakim Nivre, Yvonne Quirmbach-Brundage, Yoav Goldberg, Dipanjan Das, Kuzman Ganchev, Keith Hall, Slav Petrov, Hao Zhang, Oscar Täckström, Claudia Bedini, Núria Bertomeu Castelló, and Jungmee Lee. 2013. Universal dependency annotation for multilingual parsing. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 92–97, Sofia, Bulgaria, August. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Joakim+Nivre%2C+Yvonne+Quirmbach%2DBrundage%2C+Yoav+Goldberg%2C+Dipanjan+Das%2C+Kuzman+Ganchev%2C+Keith+Hall%2C+Slav+Petrov%2C+Hao+Zhang%2C+Oscar+Ta%CC%88ckstro%CC%88m%2C+Claudia+Bedini%2C+Nu%CC%81ria+Bertomeu+Castello%CC%81%2C+a)
13. Mehryar Mohri, Fernando Pereira, and Michael Riley. 2002. Weighted finite-state transducers in speech recognition. Computer Speech & Language, 16(1):69 – 88. [find](https://scholar.google.com/scholar?q=Mehryar+Mohri%2C+Fernando+Pereira%2C+and+Michael+Riley%2E+2002%2E+Weighted+finite%2Dstate+transducers+in+speech+recognition%2E+Computer+Speech+%26+Language%2C+16%281%29%3A69+%E2%80%93+88%2E)
14. Joakim Nivre. 2014. Universal dependencies for swedish. In Proceedings of the Swedish Language Technology Conference (SLTC), Uppsala, Sweden, November. Uppsala University, Uppsala, Sweden. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2014%2E+Universal+dependencies+for+swedish%2E+In+Proceedings+of+the+Swedish+Language+Technology+Conference+%28SLTC%29%2C+Uppsala%2C+Sweden%2C+November%2E+Uppsala+University%2C+Uppsala%2C+Sweden%2E)
15. Lilja Øvrelid and Petter Hohle. 2016. Universal dependencies for norwegian. In Nicoletta Calzolari, Khalid Choukri, Thierry Declerck, Sara Goggi, Marko Grobelnik, Bente Maegaard, Joseph Mariani, [find](https://scholar.google.com/scholar?q=Lilja+%C3%98vrelid+and+Petter+Hohle%2E+2016%2E+Universal+dependencies+for+norwegian%2E+In+Nicoletta+Calzolari%2C+Khalid+Choukri%2C+Thierry+Declerck%2C+Sara+Goggi%2C+Marko+Grobelnik%2C+Bente+Maegaard%2C+Joseph+Mariani%2C)