[lkb] LKB Type Hierarchy

[John Carroll]

On 4 Sep 2013, at 13:06, Ann Copestake wrote:

> 
>> I remember Ann saying that the algorithm was due to Carpenter and/or 
>> Penn, which would have some irony since it is not in TRALE and I am 
>> using the LKB to compute TRALE signatures.
> 
> If I recall (and I could very easily be wrong) is that Gerald Penn
> invented an algorithm independently and published it in ACL/EACL,
> stating (incorrectly) that the LKB didn't do type completion, despite
> the fact we'd had an implementation in the LKB for some years at that
> point.
> 
> Again, if I recall, the first type completion algorithm we had was one
> I invented and implemented in the LKB, which added types
> incrementally, but didn't produce an optimal solution in terms of the
> number of types.  Ulrich Callmeier then implemented a proper lattice
> solution in PET which John Carroll (I think - might have been Rob or
> perhaps oe - I'll check if anyone wants accurate information) then
> reimplemented in the LKB, replacing my code.  I think the Callmeier
> version is based on Ait-Kaci.

That's right. Ulrich Callmeier implemented Ait-Kaci's algorithm in PET, and as well as producing smaller numbers of types it ran much faster than the original LKB version. In the LKB, this processing was a major bottleneck when loading a grammar. So I also implemented the algorithm in the LKB. That was in July 2000. The approach is described in detail by Uli in the Collaborative Language Engineering book, p131-133.

John