[FOM] Logic and Linguistics

[Thomas Forster]

I heard a rumour (from Steve Pulman - now in Oxford) the the language of 
predicate calculus is contect-free or context sensitive depending on 
something subtle to do with quantifiers: whether or not one allows vacuous 
quantification, or possibly whether or not the same variable can be bound 
by different quantifiers in distinct subformulae.

  I would be glad to hear from anyone who has the exact details.




> Linguists like Barbara Hall Partee and Gerald Gazdar worked on this in the
> mid-1970s. I believe the language of first-order logic has a
> context-sensitive grammar, hence can be recognized by a linear bounded
> automaton. The main grammars, and the automata recognizing them, are
> covered in "Formal languages and their relation to automata" by John E.
> Hopcroft and Jeffrey D. Ullman (Reading, Mass., Addison-Wesley Pub. Co.
> 1969). (There is also a more recent edition with Aho as a third author.)
> 
> Neil Tennant
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 

-- 
www.dpmms.cam.ac.uk/~tf;  Home phone +44-1223-704452. 
work: +44-1223-337981. Mobile in UK +44-7887-701-562