HPSG and GPSG

[Vlado Keselj]

On Mon, 5 Jul 2004, Carl Pollard wrote:

> Right, but what I asked was about r.e. sets ("turing equivalence), not
> recursive ones.
>
> Carl

In my PhD thesis, I included a proof that HPSG is Turing-equivalent by
reducing arbitrary type 0 grammar to HPSG.  Well, the grammar that I
called "light-weight" HPSG is not precisely an HPSG (e.g., it does not
use appropriateness nor well-typedness), but the proof is general
enough that it can be easily applied to any unification-based
grammar.  The thesis can be found at:

http://www.cs.dal.ca/~vlado/papers/CS-2002-28.ps

The proof is at pages 118 and 119.
The same proof was used in:
http://www.cs.dal.ca/~vlado/snlp2000.ps

I have not been following the discussion very closely - I hope I am
not off the topic.

Best regards,

Vlado