HPSG and GPSG

[Detmar Meurers]

Hi Carl, and list members,

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.

This actually is the setup used for the Morph Moulder (MoMo) tool
for teaching the formal foundations of HPSG, cf. the paper at
      http://www.ling.ohio-state.edu/~dm/papers/rotm-fg02.html
and the page of the Milca project (producing on-line courses) at:
   http://milca.sfs.uni-tuebingen.de/A4/HomePage/English/top.html

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". It does not seem to be available on-line, but Frank can
send you a copy if you're interested.

Lieben Gruß,
Detmar

--
Detmar Meurers, Assistant Professor, Dept. of Linguistics, OSU
201a Oxley Hall, 1712 Neil Avenue, Columbus OH 43210-1298, USA
http://ling.osu.edu/~dm/                 GnuPG key on web page