[FOM] expressive power of natural languages

[Jakub Szymanik]

There is a bunch of expressibility results about quantifier fragments
of natural language, for example, ‘more than half’ is not definable in
elementary logic, even if you restrict attention to the finite
universes. One question here is to decide which GQs are realized in
NL. There has been also a lot of focus on the problem how much logic
is needed to formalize particular fragments of NL, for example some
multi-quantifier sentences. A classic example is the debate revolving
around so-called Hinitkka sentences, like “Some relative of every
townsman and some relative of every villager hate each other”
(Hintikka) or “Most villagers and most townsmen hate each other”
(Barwise).  Their branching reading is \Sigma_1^1. A good starting
point is the paper by Dag Westerstahl in Stanford Encyclopedia of
Philosophy, see:
http://plato.stanford.edu/entries/generalized-quantifiers/

Another related question might be how much resources is needed for
processing. Most quantifier constructions in NL are tractable but
still there are examples of intractable quantifier combinations, see:
http://dx.doi.org/10.1007/s10988-010-9076-z
Moreover, there is a research classifying various syllogistic
fragments of NL w.r.t computational complexity, see, e.g.,
http://dx.doi.org/10.1023/B:JLLI.0000024735.97006.5a
As far as the collective quantification is concerned, it has been
recently observed that second-order generalized quantifier MOST is not
definable in second-order logic, see:
http://dx.doi.org/10.1007/978-3-642-20920-8_20
Our earlier paper discusses some consequences for NL semantics:
http://dx.doi.org/10.1007/s10849-007-9055-0
Finally, there is some research trying to connect mathematical
predictions with linguistic and cognitive reality, see e.g.:
http://dx.doi.org/10.1111/j.1551-6709.2009.01078.x
http://dx.doi.org/10.1016/j.neuropsychologia.2005.02.012
http://dx.doi.org/10.1016/j.jcomdis.2011.07.005
http://dx.doi.org/10.1093/jos/ffp008
You may also be interested in 2 recent survey
papers:http://dx.doi.org/10.1016/B978-0-444-53726-3.00019-0http://dx.doi.org/10.1016/B978-0-444-53726-3.00020-7
Best wishes,Jakub Szymanik

-- 
Institute of Artificial Intelligence
Faculty of Mathematics and Natural Sciences
University of Groningen
P.O. Box 407
9700 AK Groningen
The Netherlands
http://www.jakubszymanik.com/
E-mail: jakub.szymanik at gmail.com