[FOM] expressive power of natural languages

Jakub Szymanik jakub.szymanik at gmail.com
Fri Dec 2 08:56:05 EST 2011

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:

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:
Moreover, there is a research classifying various syllogistic
fragments of NL w.r.t computational complexity, see, e.g.,
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:
Our earlier paper discusses some consequences for NL semantics:
Finally, there is some research trying to connect mathematical
predictions with linguistic and cognitive reality, see e.g.:
You may also be interested in 2 recent survey
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
E-mail: jakub.szymanik at gmail.com

More information about the FOM mailing list