[FOM] Logic and Linguistics
T.Forster at dpmms.cam.ac.uk
Mon Apr 2 15:08:08 EDT 2007
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
www.dpmms.cam.ac.uk/~tf; Home phone +44-1223-704452.
work: +44-1223-337981. Mobile in UK +44-7887-701-562
More information about the FOM