%-*- Mode: Latex; Default-character-style: (:SWISS :ROMAN :NORMAL) -*-
%\special{note}
\documentstyle[aaai,bezier]{article}
\newcommand{\mf}[2]{#1}
\setlength{\unitlength}{1mm}
\newcommand{\overlap}{\!\not\,\parallel}
\newcommand{\subtotal}{\not\! T}
\newcommand{\card}[1]{|#1|}

\begin{document}

\title{Mechanisms for Reasoning about Sets}
\author{Michael P. Wellman\thanks{Current address: AFWAL/AAI, Wright-Patterson AFB, OH
45433.}\\
MIT Lab for Computer Science\\
545 Technology Square\\
Cambridge, MA  02139\\
{\tt mpw@Zermatt.LCS.MIT.EDU}
\And
Reid G. Simmons\thanks{Current address: Computer Science Department, Carnegie-Mellon
University, Pittsburgh, PA 15213.}\\
MIT AI Laboratory\\
545 Technology Square\\
Cambridge, MA  02139\\
{\tt reid@OZ.AI.MIT.EDU}}

\maketitle

\begin{abstract}

The SEt Reasoning Facility ({\sc serf}) integrates mechanisms for
propagating membership propositions, deriving relations between sets, and
reasoning about closure and cardinality into an efficient utility package for
reasoning about sets.  Assertions about relations between sets are compiled
into a constraint network defined entirely in terms of union, complement,
and emptiness constraints.  The constraint network supports multiple modes
of inference, such as local propagation of membership propositions and
graph search for set relations using a transitivity table.  {\sc Serf} permits
closure assertions of the form ``all members of set $S$ are known'' and
utilizes this capability to permit selective applications of closed-world
assumptions.  Cardinality constraints are handled by a general quantity
reasoner.  An example from geologic interpretation illustrates the value of
mutually constraining sources of information in a typical application of
reasoning about sets in commonsense problem-solving.

\end{abstract}

\section{Introduction}

Sets play an important role in representing and reasoning about the
commonsense world.  Many attributes of real-world objects are naturally
represented as sets, for instance, the set of objects on top of a table, the
set of rock formations along the surface of the Earth, and the set of parents
a person has.  Reasoning about such attributes, especially about the
changes that occur to them, requires mechanisms for reasoning about:

\begin{enumerate}

\item {\em Relationships between sets}.  If the set of green blocks is
disjoint from the set of blocks in the room and the blocks on the table are a
subset of the blocks in the room, then there are no green blocks on the
table.

\item {\em Combinations of sets}.  After erosion occurs, the set 
of geologic formations on the surface of the Earth is the union of the newly
exposed formations with the initial surface formations minus those eroded
away.

\item {\em Elements of sets}.  If we know that Joe and Amy are biological
parents of John, then George cannot be a parent of John.  If Mary's parents
are Amy and Roy, then John and Mary are step-siblings.

\end{enumerate}

We have implemented mechanisms to support these and other tasks,
integrating them into the SEt Reasoning Facility ({\sc serf}).  {\sc Serf}
records facts about sets of interest and answers queries as directed by the
user or problem-solver.  {\sc serf} is designed to derive propositional facts
about particular sets---not to prove theorems about properties of sets in
general (contrast with {\sc ontic}~\cite{McAllester87}).  By keeping all
reasoning local and vivid (limited use of disjunction and negation), we gain
efficiency in doing common set-related inferences, at the cost of
completeness and generality.

A powerful feature of {\sc serf} is its integration of different types of information,
in particular ordinal relationships
(such as $\subseteq$) and set membership.  The various types
of information are mutually constraining, for instance, {\sc serf} computes ordinal
relationships from knowledge about membership and vice versa. {\sc Serf}
draws relatively weak conclusions when little information is known about the
members of a set but gives more precise answers as more detailed
information becomes available.  For example, knowing only that $C = A \cup B$ we
can infer that $|C|\leq |A|+|B|$, but given all the members of $A$ and $B$
we can determine the exact membership and cardinality of $C$.

The following section illustrates some of {\sc serf}'s capabilities with two example
applications.  The remaining sections describe the representations and algorithms
employed to achieve these results.  Section~\ref{constraint-net} introduces the
constraint network representation of set operations and describes the mechanisms
for propagating membership propositions.  Facilities for representing and deriving
relationships between sets are presented in Section~\ref{relation-section}.
Section~\ref{closure} discusses {\sc serf}'s closure mechanisms: techniques for
asserting that a set's elements are exactly those that are known members.
Reasoning about cardinality is the subject of Section~\ref{cardinality}.

\section{Applications: Two Examples}

Reasoning about sets is important in simulating and interpreting physical
situations~\cite{Simmons87}.  For example, in interpreting the sequence of
events that could form a geologic region, one must often reason about how
the set of rock formations along the surface of the Earth change as a result
of the action of geologic events, such as erosion and deposition.

\begin{figure}[thbp]
\begin{picture}(110,42)(12,4)
\put(25,45){\line(0,-1){42}}
\put(25,45){\line(3,-1){45}}
\put(25,33){\line(3,-1){45}}
\put(70,30){\line(0,-1){27}}
\put(38,3){\line(1,3){7.5}}
\put(48,3){\line(1,3){6.5}}
\put(25,3){\line(1,0){45}}
\put(25,18){\makebox(45,27){$R_1$}}
\put(25,0){\makebox(17,25){$R_2$}}
\put(38,0){\makebox(17,25){$R_3$}}
\put(48,0){\makebox(22,25){$R_4$}}

\put(10,40){\makebox(10,0){\bf (a)}}
\put(20,40){\dashbox{3}(60,0){}}
\put(80,40){\makebox(20,0){\shortstack{$TE=\emptyset$\\ $EX=\emptyset$}}}
\put(10,28){\makebox(10,0){\bf (b)}}
\put(20,28){\dashbox{3}(60,0){}}
\put(80,28){\makebox(20,0){\shortstack{$TE=\emptyset$\\ $EX\neq\emptyset$}}}
\put(10,16){\makebox(10,0){\bf (c)}}
\put(20,16){\dashbox{3}(60,0){}}
\put(80,16){\makebox(20,0){\shortstack{$S_1\subseteq TE$\\ $EX\neq\emptyset$}}}
\end{picture}
\caption{Geologic interpretation example.  The dashed lines represent
hypothetical erosion patterns.}
\label{erosion}
\end{figure}

The effect of erosion on the set of formations along the Earth's surface can
be represented by the equation $S_2 = (S_1 - TE) \cup EX$, where $S_1$ is
the set of formations on the surface before erosion, $S_2$ is the set after
erosion, $TE$ is the set of formations totally eroded away, and $EX$ is the
set of newly exposed formations that were under $S_1$ (see
Figure~\ref{erosion}).  In addition, we know that $TE$ is a subset of $S_1$
and $EX$ is disjoint from $S_1$.

In interpreting a geologic region, we are often interested in the
relationships between the various sets of rock formations, such as between
$S_2$ and $S_1$, the new and old surfaces, and between $S_2$ and the
underlying rocks $EX$.  From the above description of erosion, {\sc serf}
can infer that $S_2$ is a superset of $EX$ and that $EX$ and $TE$ are
disjoint.  That little else can be derived is to be expected since the general
description indicates nothing about the extent of erosion.  As we add more
constraints, however, {\sc serf} infers more detailed relationships.  For
example, if we assert that $TE$ and $EX$ are both empty
(Figure~\ref{erosion}, case a), {\sc serf} infers that $S_2$ is equal to
$S_1$ and disjoint from $EX$.  When we assert that $TE$ is empty but
$EX$ is not (case b -- rocks are partially eroded, exposing some underlying
formations), {\sc serf} infers that $S_2$ is a proper superset of both $S_1$
and $EX$.  Finally, asserting that $S_1\subseteq TE$ (case c -- all
formations currently on the surface are eroded away) enables {\sc serf} to
infer that $S_2=EX$.

Alternatively, {\sc serf} can reach these conclusions using constraints on
the membership of sets.  If, in conjunction with the erosion equation $S_2 =
(S_1 - TE) \cup EX$, we assert that $R_1$ is the only member of $S_1$,
that $R_2$, $R_3$, and $R_4$ are the only members of $EX$ and that
$R_1$ is a member of $TE$, {\sc serf} will conclude that
$S_2=\{R_2,R_3,R_4\}$ and thus is equal to $EX$ and disjoint from $S_1$.

We have also applied set membership reasoning to the problem of unifying
terms involving set variables.  URP, a program for reasoning about
preferences represented as utility functions~\cite{WellmanSM}, performs
goal-directed inference from a collection of utility decomposition proof rules
similar to the following:
\[(A,B\subseteq C)\wedge (A\cap B\neq\emptyset) \wedge UI(A,C-A)\wedge
UI(B,C-B)\] \[\vdash GUI(A-B,C-(A-B)).\]
For our current purposes, it is sufficient to note that $UI$ and $GUI$ are
predicates of multiattribute utility theory describing the permissible preference
interactions among sets of utility attributes.  Given a goal formula, such as
$GUI(\{x_1,x_2\},\{x_3,x_4,x_5\})$, the unification problem is to find
values of $A$, $B$, and $C$ to instantiate the premise.  To help reduce the
combinatorial search required to find unifiers, {\sc serf} is used to
constrain the members assigned to set terms.  For example, after URP binds
$A-B$ to $\{x_1,x_2\}$ and $C-(A-B)$ to $\{x_3,x_4,x_5\}$, {\sc serf}
determines that $C=\{x_1,\ldots,x_5\}$ and that $x_1$ and $x_2$ must be
contained in $A$ but not in $B$.

\section{Set Constraint Networks}\label{constraint-net}

{\sc Serf} represents assertions about sets in a constraint
network~\cite{Sussman80}.  Nodes in the network are set objects, encoding
such information as the elements that are known to be members and bounds
on the set's cardinality.  Constraint links enforce relations among the sets
they connect.

Each set is associated with four types of information:
\begin{enumerate}
\item Propositions about membership of various
elements in the set, of the form $x\in A$.
\item Whether the set is empty.
\item Whether the set is closed, that is, all of its members are known.
\item Cardinality of the set.
\end{enumerate}

All set-related propositions, are recorded in a truth maintenance system
(TMS)~\cite{McAllester80} to provide for dependency-directed updating upon
addition and deletion of assertions.  Propositions are marked {\bf true},
{\bf false}, or {\bf unknown} and are tagged with a justification for that
labeling.

The two primitive set operations supported in {\sc serf}'s constraint network
representation are {\bf union} and {\bf complement}.  These are sufficient
to represent the standard boolean set operations.  For example, the
intersection operation $A\cap B$ can be rendered in terms of our primitives
by $\overline{\bar{A}\cup\bar{B}}$, where $\bar{S}$ denotes the
complement of a set $S$ (see Figure~\ref{network-fig}).

\newsavebox{\union}
\savebox{\union}(0,0){
	\bezier{55}(0,8)(5,0)(0,-8)
	\bezier{80}(0,8)(17,7)(20,0)
	\bezier{80}(0,-8)(17,-7)(20,0) }

\begin{figure}[htbp]
\begin{picture}(100,16)(10,7)
\put(12,19){$A$}
\put(15,20){\line(1,0){8}}
\put(24,20){\circle{2}}
\put(25,20){\line(1,0){5}}
\put(30,19){$\bar{A}$}
\put(33,20){\line(1,0){8.5}} \put(12,9){$B$}
\put(15,10){\line(1,0){8}} \put(24,10){\circle{2}} \put(25,10){\line(1,0){5}}
\put(30,9){$\bar{B}$} \put(33,10){\line(1,0){8.5}}
\put(40,15){\usebox{\union}}
\put(60,15){\line(1,0){5}}
\put(65,14){$\bar{A}\cup\bar{B}$} \put(77,15){\line(1,0){5}}
\put(83,15){\circle{2}} \put(84,15){\line(1,0){5}} \put(89,14){$A\cap B$}
\end{picture}
\caption{A constraint network representing the intersection of $A$ and
$B$, built from a {\bf union} constraint (the OR gate) and three
{\bf complement} constraints (the ``inverter'' circles).}
\label{network-fig}
\end{figure}

The constraint network is used to propagate assertions about set
membership.  Given the proposition $x\in A$ (or its negation, $x\not\in A$),
the constraints determine whether $x$ is an element of sets related to $A$.
The {\bf complement} constraint ensures the equivalence of $x\in A$ and
$x\not\in\bar{A}$ using the following two disjunctive clauses:
\begin{equation}\label{complement}
x\in A \; \vee \; x\in\bar{A}
\end{equation}
\begin{equation} \label{not-complement} x\not\in A \; \vee
\; x\not\in\bar{A}.
\end{equation}
The {\bf union} constraint for $A\cup B$ is represented by three
propositional clauses: 
\begin{equation}
\label{forward-union} x\not\in{A} \; \vee \; x\in A\cup B, \end{equation}
\begin{equation} x\not\in{B} \; \vee \; x\in A\cup B, \end{equation}
\begin{equation}\label{back-union}
x\in A\;\vee \;x\in B\;\vee\;x\not\in{A\cup B}.
\end{equation}
Whenever all but one disjunct in a clause is marked {\bf false}, the
remaining proposition is declared {\bf true}.  In Figure~\ref{network-fig},
for example, asserting $x\not\in A$ implies that $x\in \bar{A}$
by~(\ref{complement}), which implies $x\in \bar{A}\cup\bar{B}$,
by~(\ref{forward-union}).  This in turn implies that $x\not\in A\cap B$,
by~(\ref{not-complement}).  We can show that our canonization of
set operations into {\bf union} and {\bf complement} constraints preserves
the membership inferences derivable from a direct implementation of the
boolean set operations.

{\sc Serf}'s membership reasoning is incomplete, however, in part due to
the locality of constraint propagation.  Suppose, for example, we assert
that $x\in B\cup C$, $x\not\in A$, and that sets $A\cup B$ and $A\cup C$
are equal.  A global analysis of the constraints reveals that $x\in B$ and
$x\in C$, since all elements not in $A$ must be in both or neither of $B$
and $C$.  This conclusion does not follow, however, by considering each
constraint individually.

The assertion language is limited in its ability to express disjunction,
negation, and quantification over sets.  For instance, we cannot encode
directly such disjunctive membership assertions as ``$x \in A\vee y \in A$.''
Although such a condition may be implied by the network as a whole in that
assertions that one is a non-member will result in the other being declared
a member, it cannot be encoded in the set node $A$ itself.  For example,
we can encode ``$x \in A\vee x \in B$'' by asserting $x \in A\cup B$.  Then
from $x \not\in A$ {\sc serf} can infer that $x \in B$.

\section{Relations Between Sets}\label{relation-section}

{\sc Serf} uses the same constraint networks to encode relations between
sets and to infer new set relationships.  For example, we can assert that
one set is a subset of another, or try to deduce whether two sets are
disjoint.  By using the same representation for reasoning about both
membership and relations, {\sc serf} exploits the mutual constraint between
the two types of information.

\subsection{Basic Relations}

Our inference mechanisms support the four binary set relationships:  subset
($\subseteq$), superset ($\supseteq$), disjoint ($\parallel$), and total
($T$)\footnote{$A\;T\;B$ means that together $A$ and $B$ span the
universe of objects.} and their respective negations: $\not\subseteq$,
$\not\supseteq$, $\overlap$, and $\subtotal$.  Table~\ref{relations}
presents their definitions in terms of set membership.  Equality is
represented as the conjunction of $\subseteq$ and $\supseteq$.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{c|c|c}
$R$ & Definition of $A\; R\; B$ & Definition of $A\not\!\! R\;B$\\
\hline
$\subseteq$ & $\forall x. x\not\in A\vee x\in B$ &
$\exists x. x\in A\wedge x\not\in B$\\
$\supseteq$ & $\forall x. x\in A\vee x\not\in B$ &
$\exists x. x\not\in A\wedge x\in B$\\
$\parallel$ & $\forall x. x\not\in A\vee x\not\in B$ &
$\exists x. x\in A\wedge x\in B$\\
$T$ & $\forall x. x\in A\vee x\in B$ &
$\exists x. x\not\in A\wedge x\not\in B$\\
\end{tabular}
\end{center}
\caption{The basic binary set relations.}
\label{relations}
\end{table}

In order to integrate knowledge about set relations with the membership
reasoning mechanisms, {\sc Serf} compiles relation assertions into networks
of {\bf union} and {\bf complement} constraints augmented by assertions
about the emptiness of sets.  For example, {\sc serf} translates $A\parallel
B$ into an assertion that the set $\overline{\bar{A}\cup\bar{B}}$ (the
intersection of $A$ and $B$) is empty.  Using the membership proposition
clauses of Section~\ref{constraint-net} in conjunction with the knowledge
that nothing is a member of the empty set, {\sc serf} enforces the
constraint that members of $A$ are not members of $B$, and vice versa.  If
we retract the disjoint assertion (by retracting the emptiness constraint),
{\sc serf} automatically withdraws support from any membership
propositions derived in this manner.  Table~\ref{compiled} lists the
constraint representations of the eight basic relations.

\renewcommand{\arraystretch}{1.2}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{c|c||c|c}
$R$ & constraint & $R$ & constraint\\ \hline
$\subseteq$ & {\it empty}$(\overline{\bar{A}\cup B})$ &
$\not\subseteq$ & {\it nonempty}$(\overline{\bar{A}\cup B})$\\
$\supseteq$ & {\it empty}$(\overline{A\cup\bar{B}})$ & $\not\supseteq$ &
{\it nonempty}$(\overline{A\cup\bar{B}})$\\
$\parallel$ & {\it empty}$(\overline{\bar{A}\cup\bar{B}})$ & $\overlap$ &
{\it nonempty}$(\overline{\bar{A}\cup\bar{B}})$\\
$T$ & {\it empty}$(\overline{{A}\cup{B}})$ & $\subtotal$ &
{\it nonempty}$(\overline{A\cup B})$\\
\end{tabular}
\end{center}
\caption{Constraint network representations of the eight basic relations.}
\label{compiled}
\end{table}

\subsection{Deriving Relations via Path Search}

Answering queries about the relations holding between sets is an important
set reasoning task.  {\sc Serf} derives set relations by composing paths of
relations in the constraint network using the transitivity of relations.  For
example, if $A$ is disjoint from $B$ and $B$ is a superset of $C$, $A$
must be disjoint from $C$ as well.  The implication of $(A\;R_1\;B)\wedge
(B\;R_2\;C)$ is $A\;(R_1\circ R_2)\;C$, where $R_1\circ R_2$ is the
relation, if any, in the cell of Table~\ref{t-table} corresponding to the row
for $R_1$ and the column for $R_2$.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{c|cccccccc}
$\circ$ & $\subseteq$ & $\not\subseteq$ & $\supseteq$ & $\not\supseteq$ &
$\parallel$ & $\overlap$ & $T$ & $\subtotal$\\
\hline
$\subseteq$ & $\subseteq$ & & & $\not\supseteq$ & $\parallel$ & & &
$\subtotal$\\
$\not\subseteq$ & & & $\not\subseteq$ & & & & $\overlap$ \\
$\supseteq$ & & $\not\subseteq$ & $\supseteq$ & & & $\overlap$ & $T$\\
$\not\supseteq$ & $\not\supseteq$ & & & & $\subtotal$ \\
$\parallel$ & & $\subtotal$ & $\parallel$ & & & $\not\supseteq$ & $\subseteq$\\
$\overlap$ & $\overlap$ & & & & $\not\subseteq$\\
$T$ & $T$ & & & $\overlap$ & $\supseteq$ & & & $\not\subseteq$\\
$\subtotal$ & & & $\subtotal$ & & & & $\not\supseteq$\\
\end{tabular}
\end{center}
\caption{The set relation transitivity table.}
\label{t-table}
\end{table}

The table is complete for chains in the following sense:  if all we know
about sets $S_1\ldots S_n$ is the chain of relations $S_i\;R_i\;S_{i+1}$,
with $i=1,\ldots,n-1$, then $R_1\circ\cdots\circ R_n$ is the strongest
implied basic relation.  In addition, the transitivity operator ($\circ$) is
associative, so relation pairs in the chains may be combined in any order.

To determine the relations holding between a pair of sets, {\sc serf}
searches the constraint network, combining the relations found on different
paths.  The search proceeds in a breadth-first manner, maintaining at each
node the set of basic relations known to hold with the starting set.  Search
proceeds from a node only if this collection of relations has been
strengthened on the incoming path.  The method is similar to that employed
by others for deriving temporal and arithmetic relations by transitivity
(e.g., \cite{Allen83a,Simmons86}).

For example, in the simple relation network of Figure~\ref{relation-net}, the
derived relation between $A$ and $D$ is the conjunction of those found on
the two paths:  $T\;\circ\not\supseteq\;=\;\overlap$ and $\supseteq\circ\;
T=T$.  Combining each of these with $D \parallel E$ yields $A\not\subseteq
E$ and $A\supseteq E$, that is, $A$ is a proper superset of $E$.  In our
path search algorithm, each set node can be visited at most four times,
once for each of the basic relations.  Because the algorithm adds no new
structure to the constraint network, its worst-case complexity is $O(r)$,
where $r$ is the number of relations asserted between sets.

\begin{figure}[htbp]
\begin{picture}(100,26)(0,0)

\put(10,11){$A$}
\put(13,12){\vector(2,1){20}}
\put(22,18){$T$}
\put(13,12){\vector(2,-1){20}}
\put(22,3){$\supseteq$}
\put(33.5,21){$B$}
\put(37,22){\vector(2,-1){20}}
\put(47,18){$\not\supseteq$}
\put(33.5,0){$C$}
\put(37,2){\vector(2,1){20}}
\put(47,3){$T$}
\put(57,11){$D$}
\put(61,12){\vector(1,0){20}}
\put(71,14){$\parallel$}
\put(81,11){$E$}

\end{picture}
\caption{A network of relations.  Path search using the transitivity table
reveals that $A\supset E$.}
\label{relation-net}
\end{figure}

As described above, {\sc serf} encodes the relations of
Table~\ref{relations} using only {\bf union}, {\bf complement}, and
emptiness constraints.  Thus, in searching this network, {\sc serf} must first
translate {\bf union} and {\bf complement} relations into the corresponding
relations of Table~\ref{t-table}.  A {\bf complement} constraint expands
into $A\parallel \bar{A}$ and $A\;T\;\bar{A}$.  A {\bf union} constraint
implies that both $A$ and $B$ are subsets of $A\cup B$.  Degenerate sets
gain some relations automatically:  $\emptyset$ is a disjoint subset of any
set, and $\bar{\emptyset}$ is a total superset.  Non-degeneracy
constraints also restrict the possible combinations of relations that can hold
between sets.  {\sc Serf} enforces the following constraints:
\[A\neq\emptyset\Rightarrow \left[ A\not\subseteq B\vee A\overlap B\right],\]
\[A\neq\bar{\emptyset}\Rightarrow\left[A\not\supseteq B\vee A\subtotal
B\right].\]
For example, if $A$ is nonempty and $A\subseteq B$, {\sc serf} deduces that
$A\overlap B$ and uses that relation in its path search algorithm.

\subsection{Deriving Relations via Membership Comparison}
\label{comparison} 

{\sc Serf} also derives relations between sets by comparing their members.
This mechanism enables {\sc serf} to deduce relationships even between
sets that are not connected in the constraint network.  For example, if $A$
is known to contain elements $x_1$, $x_2$, and $x_3$ and $B$ contains
$x_2$, $x_4$, and $x_5$, {\sc serf} concludes that $A$ and $B$ are not
disjoint, since they have an element in common.  In addition, if
$x_3\in\bar{C}$, {\sc serf} infers that $A\not\subseteq C$, since one of
the known elements of $A$ is not an element of $C$.

\begin{table}[htbp]
\begin{center}
Relationships between set $A$ and set $B$\\[1mm]
\begin{tabular}{l|c c||l|c c}
Comparison & Some & All & Comparison & Some & All\\
\hline
$A$ with $B$ & $\overlap$ & $\subseteq$ & $B$ with $A$ & $\overlap$ & $\supseteq$\\
$A$ with $\bar{B}$ & $\not\subseteq$ & $\parallel$ & $B$ with $\bar{A}$ &
$\not\supseteq$ & $\parallel$\\
$\bar{A}$ with $B$ & $\not\supseteq$ & $T$ & $\bar{B}$ with $A$ & $\not\subseteq$ & $T$\\
$\bar{A}$ with $\bar{B}$ & $\subtotal$ & $\supseteq$ & $\bar{B}$ with
$\bar{A}$ & $\subtotal$ & $\subseteq$\\
\end{tabular}
\end{center}
\caption{Using membership comparison to derive ordinal relationships.} 
\label{membcomp}
\end{table}

The necessary conditions for membership comparison can be easily derived
from Table~\ref{relations}.  For example, the definition of subset entails
that $A\subseteq B$ if all the elements of $A$ are elements of $B$ or,
conversely, if all the elements of $\bar{B}$ are elements of $\bar{A}$.
Similarly, $A\not\subseteq B$ if some element of $A$ is an element of
$\bar{B}$ or, equivalently, some element of $\bar{B}$ is an element of
$A$.  Table~\ref{membcomp} presents the complete set of conditions
needed to derive relationships by membership comparison.  In the table,
{\em some} means that at least one of the elements of the first set is a
member of the second set.  {\em All} means that all of the known members
of the first set are members of the second {\em and} that the first set is
closed, that is, the set has no members other than those explicitly
enumerated.

Performing comparison by sorting the membership lists and then iterating,
the computational complexity of this algorithm is $O(n\log n)$, where $n$ is
the number of known elements in the sets.
In the problems we have encountered, the membership comparison
mechanism is more efficient than the path search mechanism since the
number of set members are typically much less than the number of set
relations in the network.  Hence, our strategy is to use membership
comparison first and try path search only if more information remains to be
derived.

% For example, given $A = \{a, b, c\}$, $B = \{a, b, c\}$, and $d
% \in \bar{B}$, membership comparison will conclude that the basic
% relationships between $A$ and $B$ are $\subseteq$, $\supseteq$, 
% $\subtotal$, and $\overlap$.  Since the other relationships are either
% inconsistent with or subsumed by these relationships, the path search
% cannot add any more information. 

\section{Closure}\label{closure}

Asserting that a set is closed means that the only members of the set are
those currently known to the system.  The knowledge that a set is closed
adds significantly to the range of inferences {\sc serf} can perform.  For
example, in comparing the members between two sets (see
Section~\ref{comparison}), {\sc serf} cannot determine relations such as
subset or disjoint unless it is known that one of the sets is closed.
Similarly, the membership propagation constraints make use of set closure.
If $B$ is closed and $x$ is not known to be a member of $B$ (that is, the
proposition $x\in B$ is {\bf false} or {\bf unknown}), {\sc serf} infers that
$x\in\bar{B}$.  (This inference relies on an implicit {\sc serf} assumption
that all distinct terms denote distinct objects.)

Defining closure in terms of the current state of knowledge complicates
dependency maintenance.  The difficulty appears in the following situation:
suppose we assert that $x_1\in A$ and that $A$ is closed.  If we issue a
query about $x_2$, the system will respond that $x_2\in\bar{A}$, justified
by the assertions that $A$ is closed and $x_1\in A$.  If we then retract the
assertion that $A$ is closed, the TMS retracts the assertion that
$x_2\in\bar{A}$.  Thus, subsequently asserting $x_2\in A$ causes no
contradiction.  If we reassert that $A$ is closed, however, we do not want
the TMS to reassert that $x_2\in \bar{A}$, since that would conflict with the
assertion that $x_2\in A$.

To guard against such unwanted contradictions, {\sc serf} implements the
closure assertion as ``the set $S$ has exactly $n$ members.''  When a
closure assertion is made, {\sc serf} counts the number of currently known
elements and creates a closure assertion of this form.  The assertion is
justified by the current membership propositions of the set, so that the
closure is retracted if any of the membership propositions are retracted.  In
the problem above, the first assertion of closure becomes ``$A$ has exactly
one member,'' justified by $x_1\in A$, and the second ``$A$ has exactly two
members,'' justified by both memberships.  Since $x_2\in \bar{A}$ is
justified by the first assertion, closing $A$ the second time will not result
in a contradiction.

Selective application of closed-world assumptions is a useful technique in
commonsense reasoning.  {\sc Serf} enables users to make closed-world
assumptions over the members of sets through a simple extension to the
closure mechanism described above.  The only difference is that no
contradiction is raised if an object is asserted to be a member of a set
closed under the closed-world assumption.  Whenever an element is added
to or removed from such a set, {\sc serf} retracts the current closure
assumption, modifies the membership propositions, then imposes a new
closure assertion.

{\sc Serf}'s mechanism for closed-world assumptions implements a form of
non-monotonic reasoning, where conclusions drawn from a given set of
premises may become invalidated by subsequent assertions.  The underlying
TMS itself is monotonic; conclusions are withdrawn only by explicit
retraction.

\section{Cardinality}\label{cardinality}

{\sc Serf} provides mechanisms for describing and reasoning about the
cardinality of sets.  The mechanism uses the Quantity
Lattice~\cite{Simmons86} to reason about arithmetic relations, addition and
subtraction, and numeric interval constraints.  The cardinality reasoning
mechanism is a separable component of {\sc serf} in that none of the
mechanisms described above depend on cardinality information.  This gives
the user the option of not utilizing the cardinality component if the added
power (and added computational complexity) is not required.

The cardinality of a set is implemented as a quantity in the Quantity
Lattice.  The value of a quantity is constrained by its arithmetic relations
($<, \leq, >, \geq, =, \neq$) to other quantities or numbers.  Using this
mechanism, one can constrain the number of elements in a set without
specifying its exact elements.

{\sc Serf} ensures that the cardinality of a set is consistent with its
membership, emptiness, and closure constraints.  Whenever a member is
added to or removed from a set, an assertion is made that the cardinality
is greater than or equal to the number of currently known elements.  The
assertion that a set is closed implies that the upper and lower bounds on
the cardinality of the set are equal.  Conversely, if the upper bound on
cardinality is constrained to be equal to the number of known elements, the
set is asserted to be closed.  In all cases, appropriate dependencies are
recorded to facilitate retraction and explanation.

Cardinality constraints are propagated across {\bf union} relations.  Given
$A \cup B$, the system asserts $\card{A}\leq \card{A \cup B}$,
$\card{B}\leq \card{A \cup B}$, $\card{A \cup B}\leq \card{A}+\card{B}$,
$\card{\overline{A \cup B}}\leq \card{\bar{A}}$, and $\card{\overline{A
\cup B}}\leq \card{\bar{B}}$.  In addition, if the size of the universe is
known, the system asserts that the sum of the cardinalities of a set and its
complement equals the cardinality of the universal set.

The use of cardinality increases the range of inferences that {\sc serf} can
perform.  For example, if we assert that the size of the set of John's
parents is two and assert that Mary and Joe are members of the parent set
of John, then {\sc serf} can infer that George cannot be a parent of John
since that would violate the cardinality constraints.

The system can also use cardinality information to infer new relations.  For
example, knowing that $\card{A}$ is greater than $\card{B}$, the system can
infer that $A\not\subseteq B$.  Using the definitions of
Table~\ref{relations}, the implication
\[ \left[\forall x.x\not\in S_1 \vee x \in S_2\right]\Rightarrow
\card{S_1}\leq \card{S_2},\]
and the equivalence between $x\not\in S_1$ and $x\in\bar{S_1}$, we can
also derive $A\subtotal B$ from $\card{\bar{A}}>\card{B}$ and
$A\overlap
B$ from $\card{A}>\card{\bar{B}}$.  As with our other inference mechanisms, this is
an efficient but incomplete means of determining set relations.

\section{Summary}

{\sc Serf} is a utility for generic set reasoning that integrates mechanisms
for propagating membership propositions, deriving relations between sets,
and reasoning about closure and cardinality.  The central constraint network
mechanism integrates multiple sources of knowledge and supports multiple
modes of inference, such as local propagation
and path search.  We have found a comprehensive set reasoner to be
useful in several domains and expect these techniques to be applicable to
a wide variety of commonsense reasoning tasks involving sets.

\renewcommand{\baselinestretch}{1.0}\large\normalsize

\subsubsection*{Acknowledgment}

Yishai Feldman, Brian Williams, and Alex Yeh contributed helpful comments
on an earlier draft.  This work was supported by Schlumberger, National
Institutes of Health Grant No.\ R01~LM04493 from the National Library of
Medicine, and the Advanced Research Projects Agency of the Department of
Defense under Office of Naval Research contract N00014-85-K-0124.

\bibliographystyle{aaai-named}
\bibliography{abbrevs,bibcite:bibcite;bib,bibcite:bibcite;crossref}

\end{document}

some old stuff:

On the other hand, our canonization of all set operation constraints into {\bf
union} and {\bf complement} relations does not weaken inference about set
membership.  Direct implementation of intersection and set-difference
constraints, for example, would lead to no improvement over the
union-complement expansion.  Consider the symmetric-difference operation,
$sd(A,B)\equiv (A-B)\cup(B-A)$, and its expansion depicted in
Figure~\ref{symmetric-difference}.  Knowing the membership of $x$ in two
of the sets $A$, $B$, and $sd(A,B)$ is necessary and sufficient to
determine its membership in the third.  The constraint network of
Figure~\ref{symmetric-difference} captures these inferences completely,
despite the locality of propagation among constraints inside the dashed
box.

\begin{figure}[htbp]
\begin{picture}(130,42)(0,4)
\put(9,39){$A$}
\put(12,40){\line(1,0){11}}
\put(24,40){\circle{2}}
\put(25,40){\line(1,0){5}}
\put(30,39){$\bar{A}$}
\put(33,40){\line(1,0){8}}
\put(40,35){\usebox{\union}}

\put(60,35){\line(1,0){5}}
\put(65,34){$\bar{A}\cup B$}
\put(77,35){\line(1,0){4}}
\put(82,35){\circle{2}}
\put(83,35){\line(1,0){5}}
\put(88,34){$A-B$}
\put(100,35){\line(1,0){1}}
\put(101,35){\line(0,-1){5}}
\put(101,30){\line(1,0){4.5}}

\put(19,40){\line(0,-1){20}}
\put(19,20){\line(1,0){22}}
\put(21,10){\line(0,1){20}}
\put(21,30){\line(1,0){20}}

\put(9,9){$B$}
\put(12,10){\line(1,0){11}}
\put(24,10){\circle{2}}
\put(25,10){\line(1,0){5}}
\put(30,9){$\bar{B}$}
\put(33,10){\line(1,0){8}}
\put(40,15){\usebox{\union}}

\put(60,15){\line(1,0){5}}
\put(65,14){$A\cup\bar{B}$}
\put(77,15){\line(1,0){4}}
\put(82,15){\circle{2}}
\put(83,15){\line(1,0){5}}
\put(88,14){$B-A$}
\put(100,15){\line(1,0){1}}
\put(101,15){\line(0,1){5}}
\put(101,20){\line(1,0){4.5}}
\put(104,25){\usebox{\union}}

\put(124,25){\line(1,0){8}}
\put(132,24){$sd(A,B)$}

\put(16,4){\dashbox{3.5}(112,42)[br]{\it symmetric-difference}}

\end{picture}
\caption{The network expansion of symmetric difference.  No inference
power is lost in reducing the relation to {\bf union} and {\bf complement}
constraints.}
\label{symmetric-difference}
\end{figure}

  Total holds iff the complement of the
union is empty.  The network for the negation of subset, requiring a
nonemptiness constraint, is displayed in Figure~\ref{encode-relation}.

\begin{figure}[htbp]
\begin{picture}(100,26)(0,4)
\put(12,19){$A$}
\put(15,20){\line(1,0){8}}
\put(24,20){\circle{2}}
\put(25,20){\line(1,0){5}}
\put(30,19){$\bar{A}$}
\put(33,20){\line(1,0){8.5}}
\put(12,9){$B$}
\put(15,10){\line(1,0){26.5}}
\put(40,15){\usebox{\union}}
\put(60,15){\line(1,0){5}}
\put(65,14){$\bar{A}\cup B$}
\put(77,15){\line(1,0){5}}
\put(83,15){\circle{2}}
\put(84,15){\line(1,0){5}}
\put(89,12.5){\framebox(12,5){$A-B$}}

\end{picture}
\caption{The constraint network for $A\not\subseteq B$ (equivalently,
$B\not\supseteq A$).  The box enclosing $A-B$ indicates the set is
constrained to be nonempty.}
\label{encode-relation}
\end{figure}
