[FOM] Re Logic and Linguistics
fetmarsh at olypen.com
Mon Apr 2 23:04:42 EDT 2007
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
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.
Port Angeles, WA
More information about the FOM