<p>Context: <a href="http://www3.nd.edu/~dchiang/papers/synchtut.pdf" rel="nofollow">http://www3.nd.edu/~dchiang/papers/synchtut.pdf</a></p>

<p>On page 3, under the section <strong>Properties</strong>, at the end of the paragraph labeled <strong>Closure under composition?</strong>, the author mentions '<em>tree relations definable by synchronous CFGs</em>' in contrast to '<em>string relations</em>'.</p>

<p>I can't quite make out what he means here. If he hadn't made that claim, I'd have naively and happily believed that every synchronous CFG was effectively (reductively...) taking two parse trees and relating them production by production and thus trivially representing some tree-like relation.</p>

<p>What's the difference between the two?</p>

CC BY-SA 3.0
2015-10-17T22:41:09.763Z
Isn't that what is defined in section 5.1?
Michaël Cadilhac
CC BY-SA 3.0
2015-10-18T07:43:07.233Z
@MichaëlCadilhac I don't believe so. The relations representable in TSGs are a strict superset of those representable in synCFGs AFAIK, so the notion of '*tree relations definable in synchronous CFGs*' would get messy under that idea.
user
CC BY-SA 3.0
2015-10-18T10:28:15.187Z
Ah, you're right.  In Chiang's book, and in the "No Raising or Lowering" section of the paper you quote, we see an example of a tree relation definable by synchronous CFG.  What he means really is the derivation tree.  In a way, $S \to \langle U; V\rangle$ defines trees of depth 1.  This explains the remarks p. 57 of his book:
*the tree relations generated by a synchronous CFG must always have equal numbers of nonterminal nodes.*
Michaël Cadilhac
CC BY-SA 3.0
2015-10-29T09:38:29.363Z
Is that satisfactory?
Michaël Cadilhac
<context-free>
Difference between 'string relations' and 'tree relations' w.r.t. synchronous CFGs
user
# Difference between 'string relations' and 'tree relations' w.r.t. synchronous CFGs

(Asked by: username_0 on 2015-10-16)

Context: <http://www3.nd.edu/~dchiang/papers/synchtut.pdf>

On page 3, under the section **Properties**, at the end of the paragraph labeled **Closure under composition?**, the author mentions '*tree relations definable by synchronous CFGs*' in contrast to '*string relations*'.

I can't quite make out what he means here. If he hadn't made that claim, I'd have naively and happily believed that every synchronous CFG was effectively (reductively...) taking two parse trees and relating them production by production and thus trivially representing some tree-like relation.

What's the difference between the two?

**Tags:** context-free
> **Comments:**
> **username_1**: Isn't that what is defined in section 5.1?  
> **username_0**: @MichaëlCadilhac I don't believe so. The relations representable in TSGs are a strict superset of those representable in synCFGs AFAIK, so the notion of '*tree relations definable in synchronous CFGs*' would get messy under that idea.  
> **username_1**: Ah, you're right.  In Chiang's book, and in the "No Raising or Lowering" section of the paper you quote, we see an example of a tree relation definable by synchronous CFG.  What he means really is the derivation tree.  In a way, $S \to \langle U; V\rangle$ defines trees of depth 1.  This explains the remarks p. 57 of his book: *the tree relations generated by a synchronous CFG must always have equal numbers of nonterminal nodes.*  
> **username_1**: Is that satisfactory?  

---

## 0 answers

