The original ACL-06 paper gives an overview of the GHKM paper, which
I ended up cramping into just two paragraphs due to constraints on
space. I made slight changes to the terminology of GHKM (which
I mentioned in a footnote) to avoid the need to define the closure of
a span (i.e., span(closure(n))). Unfortunately, this new presentation
of GHKM leads to a different behavior in some cases.
Thanks to Liang Huang and Smaranda Muresan for pointing out an
inconsistency in the paper.
My home page links to a revised version of the paper that addresses
this issue, and that uses a terminology that is fully consistent
with the NAACL-04 paper. No other changes were made:
http://cs.stanford.edu/~mgalley/papers/acl06-sbtm.pdf
The original ACL-06 paper is here:
http://cs.stanford.edu/~mgalley/papers/acl06-sbtm-original.pdf
For readers interested in a detailed comparison, an explanation follows.
--------------------------------------------------------------------------
* Definitions in the NAACL-04 paper:
span(n): the set of words in f (the source sentence) that are reachable
from n.
closure(span(n)): the shortest contiguous span that is a superset of span(n)
complement-span(n): the union of the spans of all nodes n' in the
graph G that are neither descendants nor ancestors of n. (Note that
GHKM does not explicitly use any definition of complement-span, but
the notion is implicit).
Frontier set F: the set of all nodes of G that satisfy:
closure(span(n)) ^ complement-span(n) = \empty-set
* Definitions in the ACL-06 paper:
span(n): shorted contiguous span that includes both the first and
last word in f reachable from n.
complement-span(n): is the union of the spans of all nodes n' in the
graph G that are neither descendants nor ancestors of n.
Frontier set F: the set of all nodes of G that satisfy:
span(n) ^ complement-span(n) = \empty-set
* Comparison of ACL-06 with NAACL-04:
ACL-06's definition of span(n) is equivalent to NAACL-04's definition
of closure(span(n)), so the two conditions are seemingly equivalent:
NAACL-04: closure(span(n)) ^ complement-span(n) = \empty-set
ACL-06: span(n) ^ complement-span(n) = \empty-set
The small catch is that the definition of complement-span(n) relies
on the definition of span(n), which are different in the two papers.
Hence, F in ACL-06 is sometimes different from F in NAACL-04.
As mentioned previously, this problem has been fixed in the revision.