0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Isn't that what is defined in section 5.1? $\endgroup$
    – Michaël Cadilhac
    Commented Oct 17, 2015 at 22:41
  • $\begingroup$ @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. $\endgroup$
    – user
    Commented Oct 18, 2015 at 7:43
  • $\begingroup$ 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. $\endgroup$
    – Michaël Cadilhac
    Commented Oct 18, 2015 at 10:28
  • $\begingroup$ Is that satisfactory? $\endgroup$
    – Michaël Cadilhac
    Commented Oct 29, 2015 at 9:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.