HPSG and GPSG

[Carl Pollard]

Hi Howard, Detmar, and everyone,

To Detmar's message let me just add (paraphrase?) that HPSG uses an
expressive formalism, so the way you say that a given constraint
applies to EVERY language would be to write every grammar
in such a way that the constraint in question is a theorem.
Of course, if you KNEW IN ADVANCE which constraints those were, then
you could have designed the formalism differently, so that the theorems
in question belonged to the null theory (i.e. fell out of the
formalism). To turn it around, working in a restrictive (say CF)
formalism is a way of pretending you DO have some (in fact a lot)
of advance knowledge of this kind. A politer term for pretending
of this kind is positing a strong empirical hypothesis.

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?

Carl