Synchronous Grammars and Transducers: Good News and Bad News
What it is about
This is a short invited paper. Shieber surveys two formal approaches to relations between languages: tree transducers, and synchronous grammars. The good news is that a 2004 result connects the two through the bimorphism, so that the formalisms can be compared directly. The paper then gives two applications: synchronous grammars for the semantics of tree-adjoining grammar, and syntax-aware statistical machine translation. The bad news is that the algorithms for using these formalisms are computationally complex, possibly too complex to be practical. The paper closes with a call to the parsing technology community to make such systems practical. The text available to this card is only the first page (abstract and introduction), so the details of the applications are not summarised here, and no numbers are given.
Ideas
- I1. Put an algorithmic cost next to each component. Before a new piece is added to
tools/translate, record its time per verse and how it grows with the verse length, in the README table, since the paper's warning is about cost, not about expressiveness. - I2. A cap on the search, reported. The reader's alignment has a number of candidates per word. Set a cap, count how many verses hit it, and report the residual of those verses separately, so that the cap is not a hidden loss.
For Mova
The code is tools/translate, in the reader (hebrew.rs) and the lexicon merges (meta.rs). The card is based on a first-page extract only, so the ideas are about cost discipline, not about the paper's details. Measure the time per verse of each stage first, and report it with the residual.
Cite
@inproceedings{shieber2007synchronous,
title = {{Synchronous Grammars and Transducers: Good News and Bad News}},
author = {Shieber, Stuart},
booktitle = {Proceedings of the Tenth International Conference on Parsing Technologies},
year = {2007},
url = {https://aclanthology.org/W07-2212/}
}This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/shieber-2007-synchronous-grammars-transducers-good-news/