\documentstyle[11pt,fleqn,leqno]{article}
\setlength{\textheight}{648pt}
\setlength{\textwidth}{468pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topmargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\renewcommand{\baselinestretch}{1.5}
\renewcommand{\arraystretch}{0.8} % 1.5*0.8=1.2
\newcommand{\dfrarraystr}{.6667}
\setlength{\footnotesep}{\baselinestretch\footnotesep}
\newcommand{\cat}[1]{\mbox{{\bf #1}}}
\newcommand{\lbox}[1]{\cat{\tiny #1}}
\newcommand{\be}[1]{\begin{equation}\hspace{5mm} \mbox{#1}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bbe}[1]{\[ \hspace{5mm} \mbox{#1}}
\newcommand{\ebb}{\]}
\newcommand{\bq}{\begin{equation} \hspace{5mm}}
\newcommand{\eq}{\end{equation}}
\newcommand{\bu}{\vspace{-5mm}\[ \hspace{5mm} }
\newcommand{\eu}{\]}
\newcommand{\bi}{\vspace{-5mm}\[ \hspace{1cm} }
\newcommand{\ei}{\]}
\newcommand{\br}{\begin{rool}}
\newcommand{\er}{\end{rool}}
\newcommand{\ptq}{\mbox{\bf PTQ}}
\newcommand{\il}{\mbox{\bf IL}}
\newcommand{\PTQ}{\mbox{\bf PTQ}}
\newcommand{\IL}{\mbox{\bf IL}}
\newcommand{\GP}{\mbox{\bf GP}}
\newcommand{\GIP}{\mbox{\bf GIP}}
\newcommand{\PL}{\mbox{\bf PL}}
\newcommand{\<}[1]{(\ref{#1})}
%The following work only in math mode.
\newcommand{\prove}{\vdash}
\newcommand{\dprove}{\vdash_\Delta}
\newcommand{\ent}{\models}
\newcommand{\imp}{\models_{i}}
\newcommand{\IFF}{\leftrightarrow}
\newcommand{\AND}{\wedge}
\newcommand{\OR}{\vee}
\newcommand{\IN}{\mbox{\^{}}}
\newcommand{\EX}{\mbox{\v{}}}
\newcommand{\E}{\mbox{E}}
\newcommand{\past}{\mbox{\sc p}}
\newcommand{\future}{\mbox{\sc f}}
\newcommand{\nec}{\box}
\newcommand{\cnec}{\triangle}
\newcommand{\world}{{\cal W}}
\newcommand{\bang}{\mathop{\cup !}}
\newcommand{\VP}{\cat{e} \mid \cat{t}}
\newcommand{\vp}{\langle e, t \rangle}
\newcommand{\CN}{\cat{e} \mid \mid \cat{t}}
\newcommand{\cn}{\langle e, t \rangle}
\newcommand{\NP}{\cat{VP} \mid \cat{t}}
\newcommand{\np}{\vp, t \rangle}
\newcommand{\TV}{\cat{NP} \mid \cat{VP}}
\newcommand{\tv}{\langle \np, \vp \rangle}
\newcommand{\SCV}{\cat{t} \mid \cat{VP}}
\newcommand{\scv}{\langle \langle s,t \rangle,\vp \rangle}
\newcommand{\DT}{\cat{CN} \mid \cat{NP}}
\newcommand{\dt}{\langle \cn, \np \rangle}
\newcommand{\RFL}{\cat{TV} \mid \cat{VP}}
\newcommand{\rfl}{\langle \tv, \vp}
\newcommand{\ADJ}{\cat{e} \mid \mid \mid \cat{t}}
\newcommand{\adj}{\langle e, t \rangle}
\newcommand{\NPADV}{\cat{NP} \mid \cat{NP}}
\newcommand{\npadv}{\langle \np, \np \rangle}
\newcommand{\CNADV}{\cat{CN} \mid \cat{CN}}
\newcommand{\cnadv}{\langle \cn, \cn \rangle}
\newcommand{\ADJADV}{\cat{ADJ} \mid \cat{ADJ}}
\newcommand{\adjadv}{\langle \adj, \adj \rangle}
\newcommand{\VPADV}{\cat{VP} \mid \cat{VP}}
\newcommand{\vpadv}{\langle \vp , \vp \rangle}
\newcommand{\SADV}{\cat{t} \mid \cat{t}}
\newcommand{\sadv}{\langle \langle s, t \rangle, \vp \rangle}
\newcommand{\COND}{(\cat{t}, \cat{t}) \mid \cat{t}}
\newcommand{\cond}{\langle \langle s, t \rangle, \sadv \rangle}
\newcommand{\WHO}{\cat{(VP, NP)} \mid \cat{NP}}
\newcommand{\who}{\langle \vp, \langle \np, \np \rangle \rangle}
\newcommand{\WHAT}{\cat{(TV, NP)} \mid \cat{NP}}
\newcommand{\what}{\langle \tv, \langle \np, \np \rangle \rangle}

\newcommand{\G}{\mbox{\bf G}}
\newcommand{\T}{\mbox{\bf T}}
\newcommand{\p}{\mbox{\bf P}}
\newcommand{\M}{\cal{M}}
\newcommand{\trans}{\mapsto_q}


\begin{document}
%The defns in this file have not been changed since 30 Oct 88
%This fact is not reflected in the last changed date (ls -l)
%I have only added the NOTE to numquote and nqenum
%
%Definition for not models (moves the / to the right)
% must be used in math mode
%
\newcommand {\notmodels} {\not \! \models}
%
%Definition for definitions
\newtheorem{definition}{Definition}
%
%Definition for theorems
\newtheorem{theorem}{Theorem}[chapter]
%
%Definitions for default rule
% must be used in math mode
%
%df rule -- ***not for use in arrays***  ********************
%  (use \arrdfr in matrices)
%  requires explicit use of \displaystyle (even in arrays)
%  doesn't work correctly in arrays with a non-default value for \arraystretch
%   (the strut whose height is multiplied by \arraystretch is the height of 
%    \mathstrut not the height of the default rule)
%
\newcommand {\dfrule} [3] {\displaystyle\frac {#1 : #2} {#3}}
%
%dfarr rule -- single and multiline numerators ************** 
%  NOTE: I am using TeX boxes rather than LaTeX boxes because I don't know
%        whether the TeX height, depth, and width parameters and the
%        TeX dimensions \ht and \dp work with LaTeX boxes
% Set up a standard size mathstrut and take dimensions of box
\newbox\strbox %using TEX box because I need to refer to it later
\newlength{\stdht} \newlength{\stddp}
\setbox\strbox \hbox{$\mathstrut$}
\setlength{\stdht}{\ht\strbox} \setlength{\stddp}{\dp\strbox}
% Compute stretched dimensions (at present I believe that LaTeX takes the
%  baselineskip (which is already stretched) * arraystretch * ht(mathstrut)
%  and baselineskip (which is already stretched) * arraystretch * dp(mathstrut)
%  NOTE 1: I have found that arrays don't look very nice if they are stretched
%          too much (and they shouldn't be stretched more than the normal text)
%  NOTE 2: dfrarrstretch works inside multiline default rule numerators.
%          It takes the place of arraystretch in the LaTeX computations.
%          I find that a nice setting for dfrarrstretch is one which makes
%          baselineskip * arraystretch equal to 1 but NEVER smaller than 
%          baselineskip * arraystretch
\newlength{\extralen}
\setlength{\extralen}{\baselineskip} \addtolength{\extralen}{-\stdht}
\addtolength{\extralen}{-\stddp} \setlength{\extralen}{.5\extralen}
\newlength{\strchht} \newlength{\strchdp}
\setlength{\strchht}{\stdht} \addtolength{\strchht}{\extralen}
                                \setlength{\strchht}{\arraystretch\strchht}
\setlength{\strchdp}{\stddp} \addtolength{\strchdp}{\extralen}
\setlength{\strchdp}{\arraystretch\strchdp}
\newbox\topbox \setbox\topbox \hbox{\vrule height\strchht depth\stddp width 0pt}
\newbox\botbox \setbox\botbox \hbox{\vrule height\stdht depth\strchdp width 0pt}
%
%single line numerator
%
\newcommand {\arrdfr} [3]
             {\displaystyle \frac {\copy\topbox #1 : #2} {\copy\botbox #3}}
%
%multiline numerator
%
\newcommand{\arrstrsave}{}
\newcommand {\arrmldfr} [4]
             {\renewcommand{\arrstrsave}{\arraystretch}
              \renewcommand{\arraystretch}{\dfrarrstretch}
              \displaystyle \frac {\begin{array}[b]{@{}r@{}}
                                   \copy\topbox #1 \\ #2
                                   \end{array} : #3}
                                  {\copy\botbox #4}
              \renewcommand{\arraystretch}{\arrstrsave}}
%
%Definition for presupposition symbol
% must be used in math mode
%
\newcommand {\presupposes} {>\!\!>}
%
%Definition of the modal operators K and P
%
\newcommand{\know}{{\sf K}}
\newcommand{\poss}{{\sf P}}
%
%Definition of the modal operators Ks, Kh, Ps, Ps*
% must be used in math mode
%
\newcommand{\sknow}{{\sf K}_S}
\newcommand{\hknow}{{\sf K}_H}
\newcommand{\sposs}{{\sf P}_S}
\newcommand{\spstar}{{\sf P}_{S}^*}
%
%Definition of PsubA and PsubQ
%
\newcommand{\pa}{{\bf P$_{\!A}$}}
\newcommand{\pq}{{\bf P$_{\!Q}$}}
%
%Definition of Cn
%\newcommand{\cn}{{\it Cn}} NOT USED HERE  -- Cn defined for Surette thesis
%
%Definition of "current font style" superscript P (for presupposition)
% (if I use \scriptsize in mathmode I get a warning -- don't want this)
% (make use of the fact that the font style and size in effect before
%  entering mathmode is used in the \mbox)
%
\newcommand{\ssP}{{\scriptsize$^{\mbox{P}}$}}
%
%Definition of "current font style" superscript I (for implicature)
%
\newcommand{\ssI}{{\scriptsize$^{\mbox{I}}$}}
%
%Definition of "current font style" superscript T (for truth conditions)
%
\newcommand{\ssT}{{\scriptsize$^{\mbox{T}}$}}
%
%Definition of Hearer's Knowledge Base
% (pulls the mathmode B closer to the mathmode K)
%
\newcommand{\kbh}{$K\!B_H$}
%
%Definition of Speaker's Knowledge Base
% (pulls the mathmode B closer to the mathmode K)
%
\newcommand{\kbs}{$K\!B_S$}
%
%Definitions for numquote and nqenum (left eqno)
%                                     NOTE: it is absolutely essential to
%                                           use fleqn.sty since \mathindent
%                                           is used and it is defined in
%                                           fleqn.sty
%
\newcounter{nq}
\newenvironment{numquote}%
               {\begin{list}{(\thenq)\hfill}%
                            {\usecounter{nq}
                             \setcounter{nq}{\theequation}
                             \setlength{\leftmargin}{\mathindent}
                             \setlength{\labelwidth}{\leftmargin}
                             \addtolength{\labelwidth}{-\labelsep}
                             %test is for 9 because the label is nq + 1
                             %use \global otherwise effect of advance is local
                             \ifnum\thenq=9\newlength{\eightyeight}
                                           \settowidth{\eightyeight}{88}
                                           \newlength{\eight}
                                           \settowidth{\eight}{8}
                                           \addtolength{\eightyeight}{-\eight}
                                           \addtolength{\leftmargin}{\eightyeight}
                                           \addtolength{\labelwidth}{\eightyeight}
                                           \global\addtolength{\mathindent}
                                                              {\eightyeight}
                                           \fi
                                              }\item}%
               {\addtocounter{equation}{1}
                \end{list}}
\newcounter{nqe}
\renewcommand{\thenqe}{\thenq\alph{nqe}}
\newenvironment{nqenum}
               {\begin{numquote}%
                \begin{list}{\alph{nqe}.\hfill}%
                            {\usecounter{nqe}
                             \setlength{\leftmargin}{\leftmarginiv}
                             \setlength{\labelwidth}{\leftmargin}
                             \addtolength{\labelwidth}{-\labelsep}
                             \setlength{\topsep}{\nqetopsep}
                             \setlength{\parsep}{\nqeparsep}
                             \setlength{\partopsep}{\nqepartopsep}
                             \setlength{\itemsep}{\nqeitemsep}}}%
               {\end{list}
                \end{numquote}}
%
%Definitions for negative vspace (based on \tinyskip, \medskip, \bigskip)
%
\newcommand{\tinyshrink}  {\vspace{-\smallskipamount}}
\newcommand{\medshrink}   {\vspace{-\medskipamount}}
\newcommand{\bigshrink}   {\vspace{-\bigskipamount}}
\newcommand{\largeshrink} {\vspace{-\bigskipamount}\vspace{-\medskipamount}}
%This sets up the test for equation number 10. Upon reaching equation number 9
% (because the counter is one behind -- the use of the counter increments it)
% \mathindent is increased slightly to compensate for the increased size of the
% label
%
%this may not have to be done in single column output -- in two column the
% \mathindent is quite small
%
%this works for any pt size (10pt, 11pt, 12pt) because I take the difference in
% width between single and double digit numbers and increment everything by that
% amount (so that the gap between the label and the text remains constant)
% NOTE: this works because the label is left aligned in the label box
%
%either this or \numquote will actually do the incrementation
%
%test is for 9 because the label is nq + 1
%use \global otherwise effect of advance is local
\def\myequation{\ifnum\theequation=9\newlength{\eightyeight}
                                    \settowidth{\eightyeight}{88}
                                    \newlength{\eight}
                                    \settowidth{\eight}{8}
                                    \addtolength{\eightyeight}{-\eight}
                                    \addtolength{\leftmargin}{\eightyeight}
                                    \addtolength{\labelwidth}{\eightyeight}
                                    \global\addtolength{\mathindent}
                                                       {\eightyeight}\fi\equation}
\def\endmyequation{\endequation}
%
%Table of Contents -- same as original definition except that title is
% Table of Contents instead of Contents
%
%\newcommand{\mytableofcontents}{\@restonecolfalse\if@twocolumn\@restonecoltrue
% \onecolumn\fi\chapter*{Table of Contents\markboth
% {TABLE OF CONTENTS}{TABLE OF CONTENTS}} 
% \@starttoc{toc}\if@restonecol\twocolumn\fi}
%
%Loads various sizes of various fonts for use in math mode
%
%\load{\scriptsize}{\bf}
%
%hyphenations
%
\hyphenation{Wei-sche-del}
\hyphenation{Gun-ji}
\setcounter{page}{0}
\thispagestyle{empty}
 \null
 \vskip 2em \begin{center}
 {\Large Towards a Presuppositional Component \\
         for Montague Grammars \par} 
 \vskip 1.5em {\large \lineskip .5em
\begin{tabular}[t]{c}Philip G. Surette\footnotemark \\
                     Bell Northern Research \\
                     Ottawa, Ontario \\ %XXX XXX \\
                     surette@bnr.ca
\end{tabular} \\[1cm]
\begin{tabular}[t]{c}Robert E. Mercer\footnotemark \\
                     Department of Computer Science \\
                     Middlesex College \\
                     The University of Western Ontario \\
                     London, Ontario N6A 5B7 \\
                     (519) 679-2111 Ext. 6893 \\
                     mercer@csd.uwo.ca
\end{tabular}\par}
 \vskip 1em {\large {}} \end{center}
 \par
 \vskip 1.5em
\begin{center} \large\bf Abstract \end{center}
\renewcommand{\baselinestretch}{1} \large\normalsize
A complete analysis of an English sentence includes syntactic, semantic,
and pragmatic components. The phenomenon of presupposition belongs to the
pragmatic component. A proposition is called a presupposition of a simple
sentence if it can be inferred from both the positive and negative forms
of the simple sentence. The problem of determining the presuppositions of
complex sentences (sentences with multiple clauses) is called the projection
problem for presuppositions.

In this thesis we present a new approach to the projection problem. Our
system, based on Montague Semantics, maps sentences of a category-based
grammar into a set of expressions of intensional logic: one expression
corresponding to the literal interpretation of the sentence and the remaining
expressions corresponding to the presuppositions of the sentence. We
demonstrate that our system correctly predicts the presuppositions of a
larger range of complex sentences than previous approaches. \\[1cm]
{\large\bf Keywords:} formal theories of pragmatics, presuppositions,
                      Montague Grammars
\addtocounter{footnote}{-1}
\footnotetext{Research was performed
              while the author was at The University of Western Ontario.}
\footnotetext{Corresponding author.}
\newpage
\renewcommand{\baselinestretch}{1.5} \large\normalsize
\section{Introduction}
A complete analysis of an English sentence must have a syntactic,  semantic,
and pragmatic component. In this paper we are concerned with all three
components, but we are primarily concerned with presuppositions, a part of the 
pragmatic component of English sentences.

A proposition is said to be a {\em presupposition} of a simple sentence if
it can be pragmatically inferred from both the positive and negative forms
of the simple sentence. For instance, ``Hobbes is dead'' is a presupposition of
both \<{ex_rdr} and \<{ex_nrdr}:
\begin{numquote}\label{ex_rdr}
Calvin regrets that Hobbes is dead.
\end{numquote}
\begin{numquote}\label{ex_nrdr}
Calvin does not regret that Hobbes is dead.
\end{numquote}
The constructions that give rise to presuppositions in simple sentences are well
known. We present a partial list of these constructions in the full paper.

The question of how to determine the presuppositions of complex (multi-clause)
sentences, given that the presuppositions of simple sentences are known,
is called the {\em projection problem for presuppositions}. There have been many
attempts to solve the projection problem. To date, no attempted solution to the
projection problem has been completely successful.

Two major approaches to solving the projection problem are those based on
{\em inheritance methods} and those based on {\em cancellation methods}.
Inheritance methods calculate presuppositions syntactically. The presuppositions
of the main clause of a complex sentence are recursively calculated by transforming
the logical formulae that correspond to the presuppositions of its subclauses.  

Cancellation methods use semantic and pragmatic criteria to cancel presuppositions
of subclauses that are not presuppositions of the main clause. The presuppositions
of subclauses of a complex sentence which are inconsistent with either the semantic 
component of the sentence or with certain pragmatic components of the sentence are
cancelled (removed).  The cancellation method predicts that those
presuppositions of the subclauses of a complex sentence which are not
cancelled are the presuppositions of the main clause.

Recent attempts to solve the projection problem that have been based on
cancellation methods have been more successful predicting the 
presuppositions of complex sentences than systems based on inheritance methods.  
However, the systems that are based on cancellation methods make little or
no use of the syntactic structure of complex sentences in calculating their
presuppositions, treating complex sentences as a set of simple sentences rather
than as a grammatical structure.  Because of this, systems that are based on
cancellation methods make incorrect predictions for nested conditionals and some
sentence-complement verb constructions.

In this paper we present a new inheritance-based approach to the projection
problem which incorporates many of the strategies used in cancellation methods
but which is also sensitive to the syntactic structure of sentences.  Our system,
\GIP, maps sentences of a category-based grammar \G\ into sets of expressions of
intensional logic: one expression of the set corresponds to the literal
interpretation of the sentence and the remaining expressions correspond to the
presuppositions of the sentence. When the literal interpretation and
presuppositions of a sentence of \G\ are conjoined by the logical symbol $\AND$,
the resultant expression is called the {\em complete interpretation} of the
sentence. The sentences of \G\ are also mapped to English sentences; thus each
English sentence that is associated with one or more sentences of \G\ is
associated with an equal number of complete interpretations.

\GIP\ is essentially the system presented in Montague \cite{montague_ptq}
(hereafter referred to as \PTQ) extended to calculate the presuppositions 
of sentences as well as literal interpretations of sentences.  Thus \GIP\ can be 
regarded as an extension of Montague semantics with a pragmatic component.

Karttunen and Peters \cite{karttunen_peters79} describes an inheritance-based
system of presupposition based on \PTQ, so it is a direct precursor to \GIP.
\GIP\ improves on \cite{karttunen_peters79} by handling a much broader range of 
presuppositions than \cite{karttunen_peters79} as well as accurately predicting
the presuppositions of complex sentences for which \cite{karttunen_peters79}
makes inaccurate predictions.
  
Gazdar \cite{gazdar79} and Mercer \cite{mercer92} use cancellation methods, and 
Soames \cite{soames82} is a hybrid system that employs both inheritance methods
and cancellation methods. In the full paper we demonstrate that \GIP\ makes
accurate predictions of the presuppositions of some classes of complex sentences
for which Gazdar \cite{gazdar79}, Soames \cite{soames82}, and Mercer
\cite{mercer92} make inaccurate predictions.
\section{Representing Presuppositions in an Extended Montague \protect\\
         Grammar}\label{repn}
In the first part of the full paper we define a system, \GP, that uses the same
techniques as \PTQ\  (defined in \cite{montague_ptq}) to calculate the literal
interpretations of sentences of a category-based grammar, which in turn are
mapped to simple sentences of English. \GP\ extends \PTQ\ by calculating a set
of presuppositions for each sentence of the category-based grammar as well.
Both the literal interpretation and the presuppositions are translated into
expressions of an intensional logic. \GP\ provides a theoretical foundation for
systems such as Gazdar \cite{gazdar79} and Soames \cite{soames82} which assume
that the presuppositions of simple sentences can be calculated automatically.

In the second part of the full paper we define \GIP, which extends \GP\ by adding
inheritance conditions to some of the rules of \GP. \GIP\ also extends the grammar
of \GP\ to include the sentential connectives {\em and}\/ and {\em or}\/ and the
indicative conditional {\em if \ldots then}, so \GIP\ produces complex as well as
simple English sentences. Each presupposition that \GIP\ produces is disjoined with
a number of {\em inheritance clauses}. An inheritance clause is a modal logic
formula which is either logically true or logically false. The inheritance clauses
encode the conditions under which a presupposition should be cancelled;
cancellation is achieved by making a presupposition tautologous. By using
inheritance clauses, \GIP\ implements our inheritance-based solution to the
projection problem.

Here, we only give an example of a rule from \GP\ and a rule from \GIP\ to
provide the flavour of our proposed extension to \PTQ. The rule from \GIP\ 
attempts to show the result of adding syntactic information to the
presupposition calculation.

In the following we use the term ``presupposition(s)'' to mean the actual
presupposition(s) of the sentence. We use the term ``psupposition(s)'' to
mean the presupposition(s) of the sentence's subcomponents. The logics that we
describe are defined in the same way as that of intensional logics except that
the language contains the additional symbols ``$\cnec$'' (the {\em conditional
necessity operator}) and ``$\{_x, \}_x$'' ({\em subscripted braces}\/)
for each variable name. The type assignor is extended in the natural way for
sentences containing these symbols (described more completely in
the full paper). We do not interpret these logics directly, rather we define
a mapping $\pi$ from these logics to corresponding intensional logics which
are then interpreted in the normal way. We briefly digress to explain these
extra symbols.

\subsection{The Intended Interpretation of $\cnec$}
We let the symbol
$\cnec$ have the same interpretation as $\Box$ if it is not within the scope
of another $\cnec$ symbol, otherwise $\cnec$ has the null interpretation.
Then we let indicative conditionals of the form {\em if $A$ then $B$},
where $A$ and $B$ are statements in the present tense, be
translated by \<{conditional_cnec}, where $A'$, $B'$ are
translate $A$ and $B$, respectively.
\bq \label{conditional_cnec}
\cnec [A' \rightarrow B']
\eq
Applying \<{conditional_cnec} twice to the
embedded conditional {\em if A then if B then C}
yields the expression \<{cnec_embedded} (where $A', B', C'$
translate $A,B,C$ respectively):
\bq \label{cnec_embedded}
\cnec [A' \rightarrow \cnec [B' \rightarrow C']]
\eq
The definition of $\cnec$ gives \<{cnec_equiv}, so
\<{conditional_cnec} is the desired translation
of {\em if $A$ then $B$}.
\bq \label{cnec_equiv}
\cnec [A \rightarrow \cnec [B \rightarrow C]]
\equiv \Box [A \rightarrow (B \rightarrow C)]
\eq
Instead of giving a semantics for expressions containing
$\cnec$, we simply map such expressions into expressions
wherein each occurrence of
$\cnec$ is either replaced by $\Box$ or
removed (depending upon whether it falls into the scope of another
$\cnec$ symbol or not).  Since we are adding extra symbols to an intensional
logic, the logic without the extra symbol is an intensional logic,
$\Box$ has an interpretation in this intensional logic, and the semantics
of $\cnec$ is indirectly established.
\subsection{Interpreting Subscripted Braces $\{_x, \}_x$}
\label{grammar_brace}

For the purposes of this section, we call the expression $a$
in a pair $c=(a,b)$ the {\em binding expression} of $c$.
The set $b$ of expressions is the set of {\em bound expressions}
of $c$. Subscripted braces are a device which allows individual
variables appearing in bound expressions of a pair $c$ to be
bound by quantifiers in the binding expression of $c$.
In \GP\ the binding expression always corresponds to the
literal interpretation of a phrase of \GP, and the bound expression
always correspond to the set of psuppositions of a phrase of \GP.
Anticipating the use of subscripted variables in \GP, we wish the
pair \<{ex_lpair} to be translated (by $\pi$) into \<{fixed_lpair}
\bq \label{ex_lpair}
(\exists x \{_x \mbox{man}'(x) \}_x, \{ \{_x \mbox{adult}'(x) \}_x \})
\eq
\bq \label{fixed_lpair}
(\exists x [\mbox{man}'(x)], \{ \exists x [\mbox{man}'(x)
\rightarrow \mbox{adult}'(x)]\})
\eq
\subsection{The Mapping $\pi$}
This mapping is defined in detail in the full paper. It removes the
conditional necessity symbols and the subscripted braces in a natural
and purely (context-sensitive) syntactic way. Two examples have been
given above. In the sequel whenever we need to distinguish between the
logics with the extra symbols and without the extra symbols we will
use the prefixes \PL- (psuppositional logic) and \IL- (intensional logic),
respectively.
\subsection{\GP}
We define a {\em pair} of a typed logic
to be an ordered pair $(\alpha, \beta)$ such that $\alpha$ is
an expression of the logic and $\beta$ is a finite set of expressions
of the logic. The intended meaning for the ordered pair $(\alpha, \beta)$
is that $\alpha$ is the literal meaning of the English sentence and
$\beta$ represents the psuppositions of that sentence.
We provide here one of the rules from \GP\ to show the kind of extension
to Montague Grammars that we discussing in this paper.
\subsubsection{Rule 2: Determiners}
\label{rule_two}

\GP\ and \PTQ\ treat the indefinite and definite articles
and the quantifier {\em every} similarly.
Subscripted braces are required in order to handle the
indefinite article and {\em every} because both the indefinite article
and {\em every} are analyzed using first-order
quantification ($\exists$ and
$\forall$ respectively).  The subscripted brace notation allows
the literal and psuppositional interpretations
of the sentence to refer to
the same individual.

The treatment of the definite article given
below is similar to that given to
proper names, i.e. definite noun phrases are
treated as direct (though non-rigid) designators;
they are analyzed as a sort of descriptive demonstrative.
The phrase ``the woman'' is used as a pointer to a particular individual
and does not necessarily imply that the indicated individual is in fact a
woman but only presupposes it.  Thus it is possible to say
\be{ The woman you speak of is a male cross-dresser. }\ee
and still succeed in securing a reference, even though the psupposition that
``the woman'' is a woman is cancelled.
Similarly, it is possible to use a proper noun phrase such as ``John'' to
refer to an individual whose name is not ``John''.  Thus phrases such as
\be{ The king is not a king. }\ee
\be{ John is not called John. }\ee
can be treated quite naturally in \GP.\footnote
{Note that proper names such as {\em John}, interpreted by
$(\lambda P [P(j)],\{\lambda P [P(j)]\})$,
make use of a constant of type $e$.  It follows
from this that \GP\ treats
proper names as rigid designators.  The same analysis
is given in \PTQ.  An alternate approach is to
consider {\em John} to be short for {\em the entity
called John}, in which case the appropriate interpration
would be like a definite description:
 ($\lambda P [P(x_j)], \{\lambda P [\E(x_j)], \lambda P
[\mbox{name}'(x_j, \mbox{``John''})]\})$.}
Another attractive analysis of these
sorts of sentences which is not within the scope of
\GP\ uses quoted
text, which has the effect of suspending evaluation of the quoted phrase:
\be{ It turns out that ``the king'' is not a king at all. }\ee
\be{ ``John'' is not called John.  His name is Jeffrey. }\ee

\paragraph*{{\bf Syntactic Rule 2.1}}
If $\gamma$ is of category \cat{CN}, then $\beta$ is of type
\cat{NP} such that $\beta^r = [\mbox{a } \gamma^r]_{2.1}$.

\paragraph{{\bf Translation Rule 2.1}}
\bq[ \beta' ]_L = \lambda P [\lambda Q [\exists x \{_x(P(x) \AND Q(x)) \}_x]]
(\gamma'_L) \eq
\bq[ \beta' ]_P = \{\lambda P [\lambda Q [\{_x (Q(x) \rightarrow P(x))\}_x]]
(\psi) \mbox{ for each }\psi \in \gamma'_P\}\eq

\paragraph*{{\bf Syntactic Rule 2.2}}
If $\gamma$ is of category \cat{CN}, then $\beta$ is of type
\cat{NP} such that $\beta^r = [\mbox{the } \gamma^r]_{2.2}$.

\paragraph{{\bf Translation Rule 2.2}}
\bq[ \beta' ]_L = \lambda P [\lambda Q [Q(x_r)]] (\gamma'_L) \eq
\bq[ \beta' ]_P = \{\lambda Q [\E(x_r)],
\lambda P [\lambda Q [P(x_r)]] (\gamma'_L) \}
\cup \{\lambda P [\lambda Q
[(P(x_r)]] (\psi) \mbox{ for each } \psi \in \gamma'_P\}\eq

\paragraph*{{\bf Syntactic Rule 2.3}}
If $\gamma$ is of category \cat{CN}, then $\beta$ is of type
\cat{NP} such that $\beta^r = [\mbox{every } \gamma^r]_{2.3}$.

\paragraph{{\bf Translation Rule 2.3}}
\bq[ \beta' ]_L = \lambda P [\lambda Q [\forall x [\{_x(P(x) \rightarrow
Q(x))\}_x]]] (\gamma'_L) \eq
\bq[ \beta' ]_P = \{\lambda P [\lambda Q [\{_x P(x) \}_x]] (\psi) \mbox{ for
each } \psi \in \gamma'_P\}\eq

Note that a free variable is used in Translation Rule 2.2.
It is important that a new free variable be chosen for
each application of the rule.
Leaving the variable free
reflects that the definite article is treated as
a sort of demonstrative in \GP.  We leave it to discourse
theory to provide the value assignment for $x_r$.

The sentence \<{ex_indefinite_article} is
an example of an application of Syntactic Rule 2.1:
\bq
\label{ex_indefinite_article}
[\mbox{John } [\mbox{be } [\mbox{a bachelor
}]_{2.1}]_{\lbox{TV}(\lbox{NP}) }]_{\lbox{NP}(\lbox{VP})}
\mbox{\hspace{5mm}(which translates as ``John is a bachelor.'')}
\eq
Building the sentence from the leaves of the analysis tree
associated with \<{ex_indefinite_article} to the root, we have
\begin{eqnarray}
\lefteqn{\mbox{[a bachelor]}'_L}  \nonumber \\
     & = & \lambda P \lambda Q \exists x \{_x(P(x) \AND Q(x)) \}_x
(\lambda x [
\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND \mbox{male}'(x)] )
\nonumber  \\
     & = & \lambda Q \exists x \{_x(\mbox{unmarried}'(x) \AND
\mbox{adult}'(x) \AND \mbox{male}'(x) \AND Q(x)) \}_x \\
\lefteqn{\mbox{[a bachelor]}'_P}  \nonumber \\
          & = & \{\lambda P \lambda Q \{_x Q(x) \rightarrow
P(x)\}_x(\mbox{adult}'), \lambda P \lambda Q \{_x Q(x) \rightarrow P(x)\}_x
(\mbox{male}')\} \nonumber \\
          & = & \{\lambda Q \{_x Q(x) \rightarrow \mbox{adult}'(x)\}_x,
\lambda Q
\{_x Q(x) \rightarrow \mbox{male}'(x)\}_x\} \\
\lefteqn{\mbox{[be [a bachelor]]}'_L} \nonumber \\
          & = & \lambda W \lambda y W(\lambda z(y = z)) (\lambda Q \exists x
\{_x(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND \mbox{male}'(x) \AND
Q(x)) \}_x \nonumber \\
          & = & \lambda y \exists x \{_x(\mbox{unmarried}'(x) \AND
\mbox{adult}'(x) \AND \mbox{male}'(x) \AND (y = x))\}_x \\
\lefteqn{\mbox{[be [a bachelor]]}'_P} \nonumber \\
          & = & \emptyset \cup \{\lambda W \lambda y W(\lambda z(y = z))
(\lambda
Q \{_x Q(x) \rightarrow \mbox{adult}'(x)\}_x), \nonumber \\      &   & \lambda
W \lambda y W(\lambda z(y = z)) (\lambda Q \{_x Q(x) \rightarrow
\mbox{male}'(x)\}_x\})\} \nonumber \\
          & = & \{\lambda y \{_x (y = x) \rightarrow \mbox{adult}'(x)\}_x,
\lambda
y \{_x (y = x) \rightarrow \mbox{male}'(x)\}_x\} \\
\lefteqn{\mbox{[John [be [a bachelor]]]}'_L} \nonumber \\
          & = & \lambda P P(j) (\lambda y \exists x \{_x(\mbox{unmarried}'(x)
\AND
\mbox{adult}'(x) \AND \mbox{male}'(x) \AND (y = x))\}_x) \nonumber \\
\label{for-vpl}
          & = & \exists x \{_x(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))\}_x \\
\lefteqn{\mbox{[John [be [a bachelor]]]}'_P} \nonumber \\
          & = & \{\lambda P \E(j) (\lambda y \exists x
\{_x(\mbox{unmarried}'(x)
\AND \mbox{adult}'(x) \AND \mbox{male}'(x) \AND (y = x))\}_x)\} \nonumber \\
          &   & \mbox{} \cup \{\lambda P P(j)
(\lambda y \{_x (y = x) \rightarrow
\mbox{adult}'(x)\}_x), \nonumber \\
          &   & \lambda P P(j) (\lambda y \{_x (y = x) \rightarrow
\mbox{male}'(x)\}_x)\} \nonumber \\
\label{for-vbp}
          & = & \{\E(j), \{_x (j = x) \rightarrow \mbox{adult}'(x)\}_x,
        \{_x (j = x) \rightarrow \mbox{male}'(x)\}_x \}
\end{eqnarray}
Thus $\<{i_indefinite_article}$
is the interpretation of \<{ex_indefinite_article}:
\bq \label{i_indefinite_article}
(\exists x \{_x(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))\}_x,
\eq
\bu
\{\E(j), \{_x (j = x) \rightarrow \mbox{adult}'(x)\}_x,
        \{_x (j = x) \rightarrow \mbox{male}'(x)\}_x \})
\eu
Subscripted braces are used in the interpretation
of \<{ex_indefinite_article} to connect
the subscripted variable $x$ to the quantifier $\exists x$
which binds $x$ in the literal
interpretation of the sentence.  The procedure $\pi$ for
translating \PL-pairs containing subscripted variables
into expressions of \IL-pairs is defined in the full paper.
Applying $\pi$ to \<{i_indefinite_article} results
in the \IL-interpretation $(\<{brace_0},
\{\<{brace_5}, \<{brace_1}, \<{brace_2}, \<{brace_3}\})$.
\bq \label{brace_0}
\exists x [(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))]
\eq
\bq \label{brace_5}
\E(j)
\eq
\bq \label{brace_1}
\exists x [(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))
\rightarrow ((j = x) \rightarrow \mbox{adult}'(x))]
\eq
\bq \label{brace_2}
\exists x [(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))
\rightarrow ((j = x) \rightarrow \mbox{male}'(x))]
\eq
\bq \label{brace_3}
\exists x [(\mbox{unmarried}'(x) \AND \mbox{adult}'(x) \AND
\mbox{male}'(x) \AND (j = x))
\rightarrow ((j = x) \rightarrow \E(x))]
\eq

\subsection{\GIP}
Our goal is to define a set of psuppositional rules for \GIP\ in such a way
that none of the \IL-psuppositions that are assigned to a given phrase $\alpha$
of \GIP\ conflict with one another or with the \IL-literal interpretation of
$\alpha$. For a given phrase $\alpha$ of \GIP, where
$\pi(\alpha') = (\alpha_L'', \alpha_P'')$ and $\alpha_P'' = \{\beta_1, \ldots
\beta_n\}$, we say that the expression $\alpha_L'' \AND \beta_1 \AND \ldots
\AND \beta_n$ is the {\em complete interpretation assigned by \GIP\ to $\alpha$}.
The proposition corresponding to the complete interpretation
of a given phrase $\alpha$ of \GIP\ is our working definition of the complete
meaning of the English sentence $q(\alpha)$.

The kinds of methods that prevent psupposition conflict in \GIP\ 
(that is, to provide the proper inheritance of psuppositions) are
cancellation by contradiction, cancellation by entailment, cancellation by
a dominant psupposition, dilution, and conditionalization.
We provide here one of the rules from \GIP\ that shows cancellation by 
a dominant psupposition.
\subsubsection{\cat{SCV}(\cat{t}) Rule}
\label{rule_SCV_t}

The generating tree $t$ for the psuppositions of the complement
$\alpha$ of a sentence-complement verb are always subtrees of
$\alpha$ or the tree $\alpha$ itself.  The sentence-complement verb
introduces a new psupposition with generating tree
$t'$ such that $t'$ dominates $t$.  This is
precisely the situation in which dominant psupposition
cancellation can take place.\footnote
{In fact this situation can {\em only}\/ arise in \GIP\
when the \cat{SCV}(\cat{t}) Rule is applied.}

\paragraph*{$\mbox{\bf{Syntactic Rule}}_{\lbox{SCV}(\lbox{t})}$}

If $\alpha$ is a phrase of category \cat{SCV} and $\gamma$ is a phrase
of category \cat{t}, then $\beta$ is a phrase of category
\cat{IV} where $\beta^r = [\alpha^r \mbox{ } \gamma^r
]_{\lbox{SCV}(\lbox{t})}$.
 
\paragraph*{$\mbox{\bf{Translation Rule}}_{\lbox{SCV}(\lbox{t})}$}
 
\bq
\beta'_L = \alpha'_L(\IN \gamma'_L)
\eq
\bq
\beta'_P =
\{\psi(\IN \gamma'_L) \mbox{ for each } \psi \in \alpha'_P\}
\eq
\bu
\mbox{} \cup \{\lambda x[\psi \OR
\cnec[\phi(\IN \gamma'_L)(x) \rightarrow \neg \psi]]
\mbox{ (Dominant Psupposition Cancellation)}
\eu
\bi
\} \mbox{ for each } \psi \in \gamma'_P, \phi \in \alpha'_P
\eu

The inheritance clause works fairly simply.  In the sentence
\be{
John does not know that the king does not exist
}\ee
the psuppositions which emerge are $\E(j) \OR \ldots$, and
$\E(x_k) \OR \cnec[\neg \E(x_k) \rightarrow \neg \E(x_k)] \OR
\ldots$, and $\mbox{king}'(x_k) \OR \cnec[\neg \E(x_k)
\rightarrow \neg \mbox{king}'(x_k)] \OR \ldots$, where in each
case ``$\ldots$'' denotes a set of inheritance clauses which
after being mapped to \IL-expressions
evaluate to $\bot$.  By the meaning postulate,
$\Box[\forall x[\alpha'(x) \rightarrow \E(x)]]$\footnote{$\alpha'(x)$
translates any extensional predicate, including
(in \IL) $\mbox{walk}'$, $\mbox{married}'$, $\mbox{unmarried}'$,
$\mbox{bald}'$, $\mbox{adult'}$, $\mbox{dog}'$, $\mbox{happy}'$,
$\mbox{woman}'$, $\mbox{male}'$, and $\mbox{female}'$,
but not intensional predicates such as $\mbox{imaginary}'$.},
the last of these psuppositions is tautologized by its second clause,
so the set of psuppositions reduces to $\E(j)$.

\subsection{Discussion}
We attribute the success of our system to an integrated approach
to the syntax, semantics, and pragmatics of English sentences.
In the previous example the notion of syntactic dominance
is key to the correct working of \GIP.
\section{Conclusions}\label{conclusion}
A {\em presupposition} of a simple sentence can be inferred from both the
positive and negative forms of the simple sentence. The {\em projection problem
for presuppositions} is the problem of determining the presuppositions of
complex sentences. In the full paper we present a solution to the projection
problem for presuppositions. Our system, \GIP, is shown to predict the
presuppositions of complex sentences more accurately than any of the systems
described in \cite{gazdar79}, \cite{karttunen_peters79}, \cite{mercer92}, and
\cite{soames82}. We attribute the success of our system to an integrated approach
to the syntax, semantics, and pragmatics of English sentences. Of the other systems
examined, only \cite{karttunen_peters79} provides the same degree of integration of
these three components; however, the inheritance conditions used in
\cite{karttunen_peters79} have long been known to be faulty. \GIP\ is developed
in two stages, each stage focussing on different aspects of the projection problem.

In the first part of the full paper we define a system, \GP, that extends \PTQ\ by
calculating a set of presuppositions for each sentence of the category-based
grammar as well as the literal interpretation. In the second part of the full paper
we define \GIP, which extends \GP\ by adding inheritance conditions to some of the
rules of \GP and by including the sentential connectives {\em and}\/ and {\em or}\/
and the indicative conditional {\em if \ldots then}.

Although \GIP\ can handle many of the counterexamples to the other theories of
presupposition mentioned previously, there are still some sentences for which
\GIP\ (along with the other systems) makes incorrect predictions. In particular,
factives that have compound sentences as their complement are problematic. For
instance, \<{ex_racy} is a counterexample to all theories:
\begin{numquote}\label{ex_racy}
S: If Susan finished the race then John is not surprised that
both Susan and Mary finished the race.
\end{numquote}
The presupposition of \<{ex_racy} is {\em Mary finished the race}. Example
\<{ex_racy} is problematic because the antecedent cancels only a part of the 
presupposition of the consequent, but in \GIP\ it is not possible to reduce
the compound presupposition {\em Susan and Mary finished the race} to its
constituent parts, {\em Susan finished the race} and {\em Mary finished the race}.
It should be possible to redress this problem by representing phrases conjoined
by {\em and}\/ by {\em sets}\/ of formulae rather than by a single formula 
with multiple clauses connected with the logical symbol $\AND$. Thus each sentence
of \GIP\ would be mapped to a set of literal interpretations and a set of
presuppositions instead of to a {\em single} literal interpretation
and a set of presuppositions.
\begin{thebibliography}{1}

\bibitem{gazdar79}
{Gazdar, G.}
\newblock {\em Pragmatics: Implicature, presupposition, and logical form}.
\newblock Academic Press, 1979.

\bibitem{karttunen_peters79}
{Karttunen, L.} and S.~Peters.
\newblock Conventional implicature.
\newblock In Choon-Kyu Oh and David~A. Dinneen, editors, {\em Syntax and
  Semantics: Presupposition}, volume~11 of {\em Syntax and Semantics}, pages
  1--56. Academic Press, 1979.

\bibitem{mercer92}
{Mercer, R. E.}
\newblock A default logic approach to the derivation of natural language
  presuppositions.
\newblock Technical Report 332, The University of Western Ontario, Department
  of Computer Science, October 1992.

\bibitem{montague_ptq}
{Montague, R.}
\newblock The proper treatment of quantification in ordinary english.
\newblock In R.~H. Thomason, editor, {\em Formal Philosophy: Selected Papers of
  Richard Montague}, pages 247--270. Yale, 1970.

\bibitem{soames82}
{Soames, S.}
\newblock How presuppostions are inherited: A solution to the projection
  problem.
\newblock {\em Linguistic Inquiry}, 13(3):483--545, 1982.

\end{thebibliography}
\end{document}

