18.3.1 Store and Retrieve Approaches
One way to address the quantifier scope problem is to add a new notation to our existing semantic attachments to facilitate the compositional creation of the desired meaning representations. In this case, we'll introduce the notion of a complex-term that permits FOL expressions like $ \forall x $ Restaurant(x) to appear in places where
we would normally only allow FOL terms to appear. Formally, a complex-term will be an expression with the following three-part structure:
〈Quantifier variable formula〉
Applying this notation to our current example, we would arrive at the following representation:
$ \exists e \text{ Having}(e) $
$$ \land Haver(e,\langle\forall x\,Restaurant(x)\rangle) $$
$$ \land H a d(e,\langle\exists y M e n u(y)\rangle) $$
The intent of the this approach is to capture the basic predicate argument structure of an expression, while remaining agnostic about where the various quantifiers will end up in the final representation.
As was the case with $ \lambda $-expressions, this notational device is only useful if we can provide an algorithm to convert it back into an ordinary FOL expression. This can be accomplished by rewriting any predicate containing a complex-term according to the following schema:
$$ P(\langle\mathit{Quantifier~variable~formula}\rangle) $$
⇄
$$ \mathrm{Q u a n t i f i e r v a r i a b l e f o r m u l a C o n n e c t i v e}P(\mathrm{v a r i a b l e}) $$
In other words, the complex-term:
1. is extracted from the predicate in which it appears,
2. is replaced by the specified variable.
3. and has its variable, quantifier, and formula prepended to the new expression through the use of an appropriate connective.
The connective that is used to attach the extracted formula to the front of the new expression depends on the type of the quantifier being used: $ \land $ is used with $ \exists $, and $ \Rightarrow $ is used with $ \forall $.
How does this scheme help with our ambiguity problem? Note that our new representation contains two complex terms. The order in which we process them determines which of the two readings we end up with. Let's consider the case where we proceed left-to-right through the expression transforming the complex terms as we find them. In this case, we encounter Every restaurant first; transforming it yields the following expression.
$$ \forall x{R e s t a u r a n t}(x)\Rightarrow\exists e\;{H a v i n g}(e)\land{H a v e r}(e,x)\land{H a d}(e,\langle\exists y{M e n u}(y)\rangle) $$
Proceeding onward we next encounter a menu. Transforming this complex term yields the following final form which corresponds to the non-intuitive reading that we couldn't get with our earlier method.
$$ \exists y M e n u(y)\land\forall x R e s t a u r a n t(x)\Rightarrow\exists e~H a v i n g(e)\land H a v e r(e,x)\land H a d(e,y) $$
To get the more common-sense reading that we had earlier all we have to is pull out the complex-terms in the other order; first a menu and then every restaurant.
This approach to quantifier scope provides solutions to the two of the desiderata given earlier: complex terms provide a compact underspecified representation of all the possible quantifier-based ambiguous readings, and the method for transforming them provides a deterministic method for eliminating complex terms and thus retrieving valid FOL formulas. And by altering the ordering by which complex terms are eliminated we can recover all the possible readings. Of course, sentences with $N$ quantifiers will have $O(N!)$ different quantifier-based readings.
In practice, most systems employ an ad hoc set of heuristic preference rules that can be used to generate preferred forms in order of their overall likelihood. In cases where no preference rules apply, a left-to-right quantifier ordering that mirrors the surface order of the quantifiers is used. Domain specific knowledge can then be used to either accept a quantified formula, or reject it and request another formula. Alshawi (1992) presents a comprehensive approach to generating plausible quantifier scopings.