Synchronous Context-Free Tree Grammars
Mark-Jan Nederhof, Heiko Vogler · 2012
We consider pairs of context-free tree grammars combined through synchronous rewriting. The resulting formalism is at least as powerful as synchronous tree adjoining grammars and linear, nondeleting macro tree transducers, while the parsing complexity remains polynomial. Its power is subsumed by context-free hypergraph grammars. The new formalism has an alternative characterization in terms of bimorphisms. An advantage over synchronous variants of linear context-free rewriting systems is the ability to specify tree-to-tree transductions.