Computing Simple Quantifiers

In this Chapter I introduce the idea of semantic automata—simple computational devices corresponding to basic quantifiers in natural language. In line with a procedural approach to semantics, given a quantified sentence and a finite model, a semantic automaton computes the truth-value of this sentence in that model. In order to build the semantic automata theory, I first show how to encode finite models as strings of symbols, translating between generalized quantifier theory and formal language theory. With the help of this encoding I show what kind of automata correspond to particular quantifiers. This leads to a number of characterization results, for instance, a classic theorem of Van Benthem establishing equivalence between quantifiers definable in first-order logic (e.g., ‘more than 5’) and quantifiers recognizable by finite-automata. Quantifier ‘most’, which is not definable in first-order logic, will require a recognition device with some sort of unbounded working memory, e.g., ...