Sunday, January 23, 2011

Pregroup grammars' generative capacity

There has been a movement within mathematical linguistics toward Lambek's pregroup grammars, which were mentioned in one or two earlier posts. The book Computational Algebraic Approaches to Natural Language (Casadio & Lambek eds., 2008) collects a number of papers on this subject, and this is recommended for those who wish to catch up on the trend. The book is also available as a free download directly from the publisher Polimetrica. Myself, I am somewhat ambivalent about the framework, but there does seem to be some confusion in the literature about its generative capacity.

The first paper in the mentioned volume is "Pregroup grammars and context-free grammars" by Buszkowski and Moroz. This paper relies on a result by Buszkowski (published in the Logical Aspects of Computational Linguistics proceedings in 2001) showing the weak equivalence between pregroup grammars and context-free grammars. Yet Greg Kobele and Marcus Kracht did a paper (unpublished) showing that pregroup grammars generate the recursively enumerable languages. I asked Greg about this, and he explained (as does his paper with Kracht) that key elements of the Buszkowski result are excluding the empty string from the context-free languages, and using only free pregroups. Kobele and Kracht showed, on the other hand, that by allowing all pregroups and also allowing the empty string, one achieves Turing-equivalence, generating all r.e. languages.

This is all esoteric stuff which is nevertheless important to have nailed down when one is working with a grammar formalism. Another issue with pregroup grammars is that they deny the existence of syntactic constituents in the normal sense. But that discussion has to wait for another post.

Thursday, January 13, 2011

Russell's "No Class" theory

A fine paper by Kevin Klement on Bertrand Russell's "No Class" theory is published in the Dec. 2010 issue of the Review of Symbolic Logic. Klement outlines a sympathetic reading of Russell's attempts to eliminate actual "classes" as objects in his logical theory, showing along the way how the many high-profile criticisms of Russell (which were mostly swallowed whole by the community) fail to dislodge the No Class theory on any philosophical grounds.

Without going into technical details, Russell tried to define "propositional functions" as being open sentences of logic, such as a predicate applied to a variable as in Mortal(x). While a complete logical sentence such as Mortal(Socrates) makes the statement that Socrates is mortal, the open sentence Mortal(x) has usually been construed as equivalent to a function which maps things (substituted for x) to the statement that they are mortal. Because such a function essentially classifies things according as the resulting statement is true or false, it ends up with classes. Russell wanted to see such an expression as not involving a function or class literally, but rather as just an open sentence at face value.

I wanted to point this out here because the dichotomy between realism and nominalism is central to Klement's discussion of the No Class theory. Klement argues that while a realist philosophy compels one to accept that an open sentence is something, a nominalist position permits the consistent disavowal of that assertion. The realist, being thus compelled, is then forced to identify an open sentence with the function classifying things that could instantiate the variable, since the two are extensionally equivalent. For the realist, then, the No Class theory of open sentences is a chimera because it collapses into the same thing as having classes in the first place. The nominalist, however, permits himself to have an expression like an open sentence that doesn't correspond to something which "exists", and then is not led to an identity between open sentences and functions as maps.

The moral, for linguistic theory, is that it can be very important foundationally whether one construes a theoretical construct as representing something which exists.