HPSG and GPSG

[Carl Pollard]

Hi Detmar and everyone,

Carl wrote:

>
>One peculiarity of RSRL (which is the only fully worked out formal
> underpinning for HPSG that I have heard about) is Stephan Kepser's
> theorem that, given a grammar (presented as an RSRL theory) and
> a (syntactic encoding of) a finite interpretation, it's undecidable
> whether the interpretation satisfies the grammar. (That doesn't
> mean you can't write grammars for which satisfaction IS decidable.)
>
> Detmar, do you know of an actual proof that every r.e. language can
> expressed by an RSRL theory, or is that folklore?

After discussing these issues with Frank Richter, here we go:

What you mention as satisfaction here becomes decidable if one does
not make use of so-called chains, i.e. if one requires recursive
relations to operate only on the linguistic data structure as such
instead of any list-like data structure built from it.
>>

It needs to be made a little clearer what is meant by not making use
of chains. RSRL has chains for a reason; is there a formalism like
RSRL (i.e. with relations and "accessible" quantification") without chains
which could be used for expressing HPSG's?

>
Regarding proofs of the expressive power of (R)SRL, there is a 1997
manuscript by Paul King & Nathan Vaillette "The Expressive Power of
a Formalism for Head-Driven Phrase Structure Grammar" which in the
intro states "In the present paper, we [...] show that SRL is
capable of naturally determining any total recursive set of
strings".
>>

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

Carl