[FOM] Re Logic and Linguistics

[Ellen Fetchiet]

John Baldwin asks:  "Can one analyze first order logic in terms of phase 
structure grammars?   If so, does someone have a reference."

A good reference is Partee, ter Meulen, and Wall's "Mathematical Methods in 
Linguistics."

Looking at the syntactic complexity of fragments of first order languages 
gives examples of formal languages at various levels of the Chomsky 
hierarchy.  The set of first order formulas (for a given type) is context 
free.  Alfred Aho invented indexed grammars to handle things like variable 
binding, and the sentences of a first order language are indexed but not 
context free.  The linguist Barbara Partee asked if the set of first order 
formulas in which every quantifier actually binds something is indexed.  She 
and I conjectured in 1984 that it is not.  As far as I know, that question 
is still open.

Baldwin also says:  "On the other hand, some `Chomskian' positions claim 
(e.g. Devlin, The Math Gene page 157) that phase structure grammars give an 
underlying structure for all natural languages."

That question is the subject of the anthology "The Formal Complexity of 
Natural Language" edited by Walter Savitch et al.



Bill Marsh

Port Angeles, WA

360-457-6758