--- title: "Synchronous Grammars as Tree Transducers — Shieber 2004" description: "Tree transducers came from formal language theory as generalisations of finite-state transducers to trees. Synchronous tree substitution and adjoining…" authors: ["Stuart M. Shieber"] year: 2004 venue: "Proceedings of the 7th International Workshop on Tree Adjoining Grammar and Related Formalisms" source: "https://aclanthology.org/W04-3312/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/shieber-2004-synchronous-grammars-as-tree-transducers/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/shieber-2004-synchronous-grammars-as-tree-transducers/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2004](https://md.research.elamur.ai/free/en/papers/2004/) / Synchronous Grammars as Tree Transducers # Synchronous Grammars as Tree Transducers **Authors:** [Stuart M. Shieber](https://md.research.elamur.ai/free/en/authors/stuart-m-shieber/) · **Year:** 2004 · **Venue:** Proceedings of the 7th International Workshop on Tree Adjoining Grammar and Related Formalisms **Link:** [aclanthology.org/W04-3312](https://aclanthology.org/W04-3312/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only [**24** citations in our library](https://md.research.elamur.ai/free/en/papers/shieber-2004-synchronous-grammars-as-tree-transducers/cited-by/) of the 140884 papers whose bibliographies we read · [Proceedings of the 7th International Workshop on Tree Adjoining Grammar and Related Formalisms](https://aclanthology.org/volumes/W04-33/) · [licence](https://creativecommons.org/licenses/by-nc-sa/3.0/) - [Publisher's page](https://aclanthology.org/W04-3312/) - [PDF](https://aclanthology.org/W04-3312.pdf) **Authors (1)** 1. Shieber, Stuart M. [Semantic Scholar](https://www.semanticscholar.org/author/1692491) Citations and author metrics: OpenAlex, ; authors with the same name are not always told apart. ## What it is about Tree transducers came from formal language theory as generalisations of finite-state transducers to trees. Synchronous tree substitution and adjoining grammars came from computational linguistics as a way to pair syntactic structures. Shieber unifies the two lines by means of the bimorphism, a construct in which a regular tree language is mapped to two output trees by two homomorphisms. The main result is that synchronous tree substitution grammars are equivalent to bimorphisms in which both component homomorphisms are linear and complete. Linear means that no input node is copied, and complete means that no input node is deleted without being mapped. The paper proves the equivalence in both directions and discusses the consequences for the classes of tree relations that each formalism can describe. It has no experiments. ## Ideas - I1. A checker for the translator's rule tables. For each rule, verify that it is linear (no meta token is used twice) and complete (every source token is mapped or explicitly deleted). A rule that fails either test is printed with its id, so the reader and encoder can be audited. - I2. Deletions made explicit. Completeness says that a dropped source word must be mapped to nothing on purpose. Give the reader a null-concept token for each deleted function word, and count them per author, which is the same need as open problem 4. - I3. Separate reader and encoder as two homomorphisms on a shared intermediate tree. The meta-world is that tree. Keep the interface between `tools/translate` reader and encoder as one shared tree type, so the bimorphism view holds in the code. ## For Mova The code is `tools/translate` (the meta-world is the shared tree). The paper is theoretical, so no number is claimed. The first step is the counting checker of I1 on the current rule tables: report how many rules are not linear and how many source tokens are not mapped, and run the count twice to check it is stable. Topics: [Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/) ## Cite The paper itself, not this card. BibTeX from the library's record of the work. ```bibtex @inproceedings{shieber2004synchronous, title = {{Synchronous Grammars as Tree Transducers}}, author = {Shieber, Stuart M.}, booktitle = {Proceedings of the 7th International Workshop on Tree Adjoining Grammar and Related Formalisms}, year = {2004}, url = {https://aclanthology.org/W04-3312/} } ``` - [← previous SVMTool: A general POS Tagger Generator Based on Support Vector Machines](https://md.research.elamur.ai/free/en/papers/gimenez-2004-svmtool-general-pos-tagger-generator/) - [next → The Automatic Content Extraction (ACE) Program – Tasks, Data, and Evaluation](https://md.research.elamur.ai/free/en/papers/doddington-2004-automatic-content-extraction-ace-program/) - [↑ back to papers of 2004](https://md.research.elamur.ai/free/en/papers/2004/) ## References 5 references, 3 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. A. Arnold and M. Dauchet. 1982. Morphismes et bi-morphismes d’arbres. Theoretical Computer Science, 20(1):33–93, March. [find](https://scholar.google.com/scholar?q=A%2E+Arnold+and+M%2E+Dauchet%2E+1982%2E+Morphismes+et+bi%2Dmorphismes+d%E2%80%99arbres%2E+Theoretical+Computer+Science%2C+20%281%29%3A33%E2%80%9393%2C+March%2E) 2. H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. 1997. Tree automata techniques and applications. Available at: [http://www.grappa.univ-lille3.fr/tata](http://www.grappa.univ-lille3.fr/tata). release of October 1, 2002. [↗](http://www.grappa.univ-lille3.fr/tata) 3. Jason Eisner. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, Sapporo, Japan, July. [find](https://scholar.google.com/scholar?q=Jason+Eisner%2E+2003%2E+Learning+non%2Disomorphic+tree+mappings+for+machine+translation%2E+In+Proceedings+of+the+41st+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+Sapporo%2C+Japan%2C+July%2E) [our card](https://md.research.elamur.ai/free/en/papers/eisner-2003-learning-non-isomorphic-tree-mappings/) 4. Mehryar Mohri. 1997. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269–311. [find](https://scholar.google.com/scholar?q=Mehryar+Mohri%2E+1997%2E+Finite%2Dstate+transducers+in+language+and+speech+processing%2E+Computational+Linguistics%2C+23%282%29%3A269%E2%80%93311%2E) [our card](https://md.research.elamur.ai/free/en/papers/mohri-1997-finite-state-transducers-language-speech/) 5. Stuart M. Shieber. 1992. Restricting the weak-generative capacity of synchronous tree-adjoining grammars. In Proceedings of the Second TAG Workshop, University of Pennsylvania, Philadelphia, Pennsylvania, June 24– 26. [find](https://scholar.google.com/scholar?q=Stuart+M%2E+Shieber%2E+1992%2E+Restricting+the+weak%2Dgenerative+capacity+of+synchronous+tree%2Dadjoining+grammars%2E+In+Proceedings+of+the+Second+TAG+Workshop%2C+University+of+Pennsylvania%2C+Philadelphia%2C+Pennsylva) [our card](https://md.research.elamur.ai/free/en/papers/shieber-1990-synchronous-tree-adjoining-grammars/)