A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses (...) of natural language quantifiers. We also determine the state complexity of iteration of regular languages. (shrink)

The paper proposes the first unified account of deictic/sentence-external and sentence-internal readings of singular different . The empirical motivation for such an account is provided by a cross-linguistic survey and an analysis of the differences in distribution and interpretation between singular different , plural different and same (singular or plural) in English. The main proposal is that distributive quantification temporarily makes available two discourse referents within its nuclear scope, the values of which are required by sentence-internal uses of singular different (...) to be distinct, much as its deictic uses require the values of two discourse referents to be distinct. Thus, we take sentence-internal readings to be a form of ‘association with distributivity’ that is similar to association with focus. The contrast between singular different , plural different and same is explained in terms of several kinds of quantificational distributors that license their internal readings. The analysis is executed in a stack-based dynamic system couched in type logic, so we get compositionality in the usual Montagovian way. Quantificational subordination and dependent indefinites in various languages provide additional motivation for the account. Investigating the connections between items with sentence-internal readings and the quantificational licensors of these readings opens up a larger project of formally investigating (i) the typology of quantificational distributors and distributivity-dependent items and (ii) the fine-grained contexts of evaluation needed to capture this typological variation. (shrink)

Functions of type n are characteristic functions on n-ary relations. Keenan [5] established their importance for natural language semantics, by showing that natural language has many examples of irreducible type n functions, i.e., functions of type n that cannot be represented as compositions of unary functions. Keenan proposed some tests for reducibility, and Dekker [3] improved on these by proposing an invariance condition that characterizes the functions with a reducible counterpart with the same behaviour on product relations. The present paper (...) generalizes the notion of reducibility (a quantifier is reducible if it can be represented as a composition of quantifiers of lesser, but not necessarily unary, types), proposes a direct criterion for reducibility, and establishes a diamond theorem and a normal form theorem for reduction. These results are then used to show that every positive n function has a unique representation as a composition of positive irreducible functions, and to give an algorithm for finding this representation. With these formal tools it can be established that natural language has examples of n-ary quantificational expressions that cannot be reduced to any composition of quantifiers of lesser degree. (shrink)