Synchronous Grammars as Tree Transducers

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

Cite

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

@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/}
}

References

5 references, 1 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
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. release of October 1, 2002. ↗
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 our card
4. Mehryar Mohri. 1997. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):269–311. find
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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/shieber-2004-synchronous-grammars-as-tree-transducers/