A formal study of the problem of why some natural language sentences are harder to understand than others is the objective of this book. In that, it claims to be a highly interdisciplinary approach to language complexity. And, in terms of its motivation, it certainly is very interdisciplinary. It aims to study the semantic complexity of natural language, trying to understand why some natural language sentences are harder to understand than others. It focuses on the complexity of natural language quantifiers.
The main approach follows the tradition of philosophers such as Frege [1], who viewed the meaning of sentences as a procedure to find truth, and finds guidance in the tradition that followed from that idea. The focus of the research is in computational linguistics, finding its main support in Ristad’s thesis [2] that natural language expressions are limited in complexity to a class of languages that express all NP-complete queries. On the linguistic side, it focuses on Lindström’s theory of generalized quantifiers [3].
The first part of the book (actually, this covers Parts 1 and 2) covers all those motivational aspects in adequate depth. Furthermore, the book presents psychological motivation from neurocognitive evidence coming from experiments measuring reaction times for understanding natural language sentences containing different levels of quantifiers.
However, this book is really about the descriptive complexity of generalized quantifiers, and the final part of the book (chapters 6 to 9) leaves behind those motivational issues and presents several results about the descriptive complexity of formulas containing several kinds of generalized quantifiers.
Polyadic quantifiers, a subclass of generalized quantifiers, are studied in chapters 6 and 7; conditions for PTIME descriptive complexity of operators on quantifiers (polyadic lifts) are presented. Several other quantifiers that lie outside the range of the PTIME-preserving operators are studied (so-called Henkin quantifiers, Ramsey quantifiers, and branching quantifiers, among others); all of those quantifiers lie within the limits imposed by Ristad’s thesis.
Collective quantifiers, namely those involved in the quantification of collections of objects, are shown to present a greater challenge. In fact, by their very nature of dealing with sets of elements, they are second-order operators in terms of formal logic. However, it is discussed in chapter 10 that the quantifier MOST is not definable in second order. On the one hand, this result explains the difficulties in understanding certain natural language sentences involving majority; on the other hand, this challenges Ristad’s thesis. The author discusses that this type of quantification may lie outside the realm of “everyday language,” and thus the validity of that thesis still holds for “normal” language. Several open problems are discussed with regard to what “everyday language” consists of.
Overall, the book is full of ideas; it is based on the philosophical and linguistic literature; and it pushes the boundary of what can be formally described and explained in terms of natural language expressions. It is unavoidable that the technical discussion occurs in a heavily mathematical arena, in this case in terms of descriptive logic complexity, but it is commendable that the results of that discussion may be transported outside the limits of that arena and find application in a truly interdisciplinary subject such as natural language studies.