\documentstyle[jair,psfig,twoside,11pt,theapa]{article}
\input epsf %% at top of file

\jairheading{5}{1996}{239-288}{3/96}{11/96}
\ShortHeadings{MUSE CSP: An Extension to the Constraint Satisfaction Problem}
{Helzerman \& Harper}
\firstpageno{239}


% \begin{Formula} 
                  
\makeatletter      
\def\@doyoavspecials{\do\ \do\&\do\#\do\%\do\~}

\def\@formula{\trivlist \item[]\if@minipage \vskip \z@ \else\vskip
\z@\fi 
\leftskip\@totalleftmargin\rightskip\z@
\parindent\z@\parfillskip\@flushglue \parskip\z@
\obeylines \tt \let\do\@makeother \@doyoavspecials}

%\@tempswafalse \def\par{\if@tempswa\hbox{}\fi\@tempswatrue\@@par}

 
\def\formula{\@formula \frenchspacing\@vobeyspaces}
\let\endformula=\endtrivlist

\newenvironment{constraint}{\renewcommand{\baselinestretch}{.75}\noindent\begin{minipage}{\textwidth}\begin{formula}}{\end{formula}\end{minipage}\renewcommand{\baselinestretch}{1.0}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}


\def\singlespace{\def\baselinestretch{1.0}}
\def\endsinglespace{}

\newcounter{linecount}
\newcommand{\lct}{\protect\refstepcounter{linecount} \protect\thelinecount.  }
\newcommand{\lctl}[1]{\protect\refstepcounter{linecount} \protect\thelinecount.
  \protect\label{#1}}
%  \newcommand{\initlct}{\protect\setcounter{linecount}{-1}}    %% 1st # is 0
\newcommand{\initlct}{\protect\setcounter{linecount}{0}}        %% 1st # is 1


\begin{document}

\title{MUSE CSP: An Extension to\\
the Constraint Satisfaction Problem}

\author{\name Randall A. Helzerman \email helz@ecn.purdue.edu \\
       \name Mary P. Harper \email harper@ecn.purdue.edu \\
       \addr School of Electrical and Computer Engineering\\
	1285 Electrical Engineering Building\\
        Purdue University\\
        West Lafayette, IN 47907-1285 USA}


\maketitle

\begin{abstract}
This paper describes an extension to the constraint satisfaction
problem (CSP) called MUSE CSP ({\em MU\/}ltiply {\em SE\/}gmented {\em
C\/}onstraint {\em S\/}atisfaction {\em P\/}roblem).  This extension
is especially useful for those problems which segment into multiple
sets of partially shared variables.  Such problems arise naturally in
signal processing applications including computer vision, speech
processing, and handwriting recognition.  For these applications, it
is often difficult to segment the data in only one way given the
low-level information utilized by the segmentation algorithms.  MUSE
CSP can be used to compactly represent several similar instances of
the constraint satisfaction problem.  If multiple instances of a CSP
have some common variables which have the same domains and
constraints, then they can be combined into a single instance of a
MUSE CSP, reducing the work required to apply the constraints.  We
introduce the concepts of MUSE node consistency, MUSE arc consistency,
and MUSE path consistency. We then demonstrate how MUSE CSP can be
used to compactly represent lexically ambiguous sentences and the
multiple sentence hypotheses that are often generated by speech
recognition algorithms so that grammar constraints can be used to
provide parses for all syntactically correct sentences.  Algorithms
for MUSE arc and path consistency are provided.  Finally, we discuss
how to create a MUSE CSP from a set of CSPs which are labeled to
indicate when the same variable is shared by more than a single CSP.
\end{abstract}



\section{Introduction}

This paper describes an extension to the constraint satisfaction
problem (CSP) called MUSE CSP ({\em MU\/}ltiply {\em SE\/}gmented {\em
C\/}onstraint {\em S\/}atisfaction {\em P\/}roblem).  This extension
is especially useful for those problems which segment into multiple
sets of partially shared variables. First, we describe the constraint
satisfaction problem and then define our extension.

\subsection{The Constraint Satisfaction Problem}

Constraint satisfaction problems (CSP) have a rich history in
Artificial Intelligence
\cite{davisandrosenfeld,dechtermeiriandpearl,dechterandpearl,freuder89,freuder90,mackworth77,mackworthandfreuder,villainandkautz,waltz75}
(for a general reference, see Tsang, 1993).  Constraint satisfaction
provides a convenient way to represent and solve certain types of
problems. In general, these are problems which can be solved by
assigning mutually compatible values to a predetermined number of
variables under a set of constraints.  This approach has been used in
a variety of disciplines including machine vision, belief maintenance,
temporal reasoning, graph theory, circuit design, and diagnostic
reasoning.  When using a CSP approach (e.g., Figure
\ref{map_coloring}), the variables are typically depicted as vertices
or nodes, where each node is associated with a finite set of possible
values, and the constraints imposed on the variables are depicted
using arcs.  An arc looping from a node to itself represents a unary
constraint (a constraint on a single variable), and an arc between two
nodes represents a binary constraint (a constraint on two variables).
A classic example of a CSP is the map coloring problem (e.g., Figure
\ref{map_coloring}), where a color must be assigned to each country
such that no two neighboring countries have the same color.  A
variable represents a country's color, and a constraint arc between
two variables indicates that the two joined countries are adjacent and
should not be assigned the same color.
\begin{figure}[b]
\centerline{\psfig{figure=map_coloring.ps,height=1.4in}}
\caption{The map coloring problem as an example of CSP.}
\label{map_coloring}
\end{figure}

	Formally, a CSP \cite{mackworth77} is defined in Definition 1.
{\small \renewcommand{\baselinestretch}{.95}
\begin{definition}{\em (Constraint Satisfaction Problem)}\\
\noindent \begin{tabular}{l}
$N = \{i, j, \ldots \}$ is the set of {\em nodes} (or variables), with $|N|=n$, \\
$L = \{a, b, \ldots \}$ is the set of {\em labels}, with $|L|=l$, \\
$L_{i} = \{a | a \in L$ and $(i,a)$ is admissible$\}$, \\
$R{\it 1}$ is a {\em unary constraint}, and $(i,a)$ is admissible if $R{\it 1}(i,a)$,\\
$R{\it 2}$ is a {\em binary constraint}, $(i,a)-(j,b)$ is admissible 
if $R{\it 2}(i,a,j,b)$.\\
\end{tabular}
\end{definition}}

%\renewcommand{\baselinestretch}{1.5}
\noindent A CSP network contains all $n$-tuples in $L^{n}$ which
satisfy $R{\it 1}$ and $R{\it 2}$.  Since some of the labels
associated with a node may be incompatible with labels assigned to
other nodes, it is desirable, when the constraints are sufficiently
tight \cite{vanbeek}, to eliminate as many of these labels as possible
by enforcing local consistency conditions before a globally consistent
solution is extracted \cite{dechter92}.  Node and arc consistency are
defined in Definitions \ref{node_consistency_def} and
\ref{arc_consistency_def}, respectively.  In addition, it may be
desirable to eliminate as many label pairs as possible using path
consistency, which is defined in Definition
\ref{path_consistency_def}.


{\small \renewcommand{\baselinestretch}{.95}\begin{definition}{\em (Node Consistency)}
An instance of CSP is said to be {\em node consistent} if and only if each
node's domain contains  only  labels for which the unary
constraint $R{\it 1}$ holds, i.e.: \[\forall i \in N : \forall a \in
L_{i} : R{\it 1}(i,a)\]
\label{node_consistency_def}
\end{definition}}
{\small \renewcommand{\baselinestretch}{.95}\begin{definition}{\em (Arc Consistency)}
An instance of CSP is said to be {\em arc consistent} if and only
if for every pair of nodes $i$ and $j$, each element of $L_{i}$ (the
domain of $i$) has at least one element of $L_{j}$ for which the
binary constraint $R{\it 2}$ holds, i.e.: \[\forall i,j \in N: \forall a
\in L_{i} : \exists b \in L_{j} : R{\it 2}(i,a,j,b)\]
\label{arc_consistency_def}
\end{definition}}
{\small \renewcommand{\baselinestretch}{.95}\begin{definition}{\em (Path Consistency)}
An instance of CSP is said to be {\em path consistent} if and only
if:\\ \\
$\forall i,j \in N: i \neq j \Rightarrow (\forall a \in L_{i}: \forall b \in
L_{j}:  \forall k \in N: k \neq i \wedge k \neq j \wedge Path(i,k,j)
\Rightarrow \\
\hspace*{.5in} $(R{\it 2}(i,a,j,b)$ \Rightarrow \exists c \in L_{k}:
R{\it 2}(i,a,k,c) \wedge  R{\it 2}(k,c,j,b)))$\\ \\
where Path$(i,k,j)$ indicates that there is a path of arcs of length
two connecting $i$ and $j$ which goes through $k$.
\label{path_consistency_def}
\end{definition}} 

%\renewcommand{\baselinestretch}{1.5}
Node consistency is easily enforced by the operation $L_{i}=L_{i} \cap
\{x|R{\it 1}(i,x)\}$, requiring O$(nl)$ time (where $n$ is the number
of variables and $l$ is the maximum domain size).  Arc consistency is
enforced by ensuring that every label for a node is supported by at
least one label for each node with which it shares a binary constraint
\cite{mackworth77,mackworthandfreuder,ac4paper}. The arc consistency
algorithm AC-4 \cite{ac4paper} has an worst-case running time of
$\Theta(el^{2})$ (where $e$ is the number of constraint arcs). AC-3
\cite{mackworthandfreuder} often performs better than AC-4 in
practice, though it has a slower running time in the worst case.  AC-6
\cite{bessiere94} has the same worst-case running time as AC-4 and is
faster than AC-3 and AC-4 in practice.  Path consistency ensures that
any pair of labelings $(i,a)-(j,b)$ allowed by the $(i,j)$ arc
directly are also allowed by all arc paths from $i$ to $j$.  Montanari
has proven that to ensure path consistency for a complete graph, it
suffices to check every arc path of length two \cite{montanari}.  The
path consistency algorithm PC-4 \cite{hanandlee} has a worst-case
running time of O($n^{3}l^{3}$) time (where $n$ is the number of
variables in the CSP).

\subsection{The Multiply Segmented Constraint Satisfaction Problem}

There are many types of problems which can be solved by using CSP in a
more or less direct fashion.  There are also problems which might
benefit from the CSP approach, but which are difficult to represent
with a single CSP.  This is the class of problems our paper addresses.
For example, suppose the map represented in Figure \ref{map_coloring}
is scanned by a noisy computer vision system, with a resulting
uncertainty as to whether the line between regions 1 and 2 is really a
border or an artifact of the noise.  This situation would yield two
CSP problems as depicted in Figure \ref{ambiguous_map_coloring}. A
brute-force approach would be to solve both of the problems, which
would be reasonable for scenes containing only a few ambiguous
borders.  However, as the number of ambiguous borders increases, the
number of CSP networks would grow in a combinatorially explosive
fashion.  In the case of ambiguous segmentation, it can be more
efficient to merge the constraint networks into a single network which
would compactly represent all of the instances simultaneously, as
shown in Figure \ref{combo}.  Notice that the CSP instances are
combined into a directed acyclic graph where the paths through the DAG
from start to end correspond to those CSPs that were combined.  In
this paper, we develop an extension to CSP called MUSE CSP ({\em
MU\/}ltiply {\em SE\/}gmented {\em C\/}onstraint {\em S\/}atisfaction
{\em P\/}roblem), which represents multiple instances of a CSP problem
as a DAG.
\begin{figure}
\centerline{\psfig{figure=ambiguous_map_coloring.ps,height=2.5in}}
\caption{An ambiguous map yields two CSP problems.}
\label{ambiguous_map_coloring}
\end{figure}
\begin{figure}
\centerline{\psfig{figure=combo.ps,width=6.5in}}
\caption{How the two CSP problems of Figure 2 can be captured by a
single instance of MUSE CSP.
The directed edges form a DAG such that the directed paths through the DAG
correspond to instances of those CSPs that were combined.} 
\label{combo}
\end{figure}

     If there are multiple, similar instances of a CSP, 
then separately applying constraints for each instance can 
result in much duplicated work.  To avoid this
duplication, we have provided a way to combine the multiple instances
of CSP into a 
MUSE CSP, and we have developed the concepts of MUSE node consistency,
MUSE arc consistency, and MUSE path consistency.
Formally, we define MUSE CSP as follows:

%\renewcommand{\baselinestretch}{.95}
{\small \renewcommand{\baselinestretch}{.95} \begin{definition}{\em (MUSE CSP)}
\\
\begin{tabular}{l}
$N = \{i, j, \ldots \}$ is the set of {\em nodes} (or variables), with $|N|=n$, \\
$\Sigma \subseteq 2^{N}$ is a set of {\em segments} with $|\Sigma|=s$, \\
$L = \{a, b, \ldots \}$ is the set of {\em labels}, with $|L|=l$, \\
$L_{i} = \{a | a \in L$ and $(i,a)$ is admissible in at least one segment\}, \\
$R{\it 1}$ is a unary constraint, and $(i,a)$ is
admissible if $R{\it 1}(i,a)$, \\
$R{\it 2}$ is a binary constraint, $(i,a)-(j,b)$ is admissible if 
$R{\it 2}(i,a,j,b)$. \\
\end{tabular}
\end{definition}}
%\renewcommand{\baselinestretch}{1.5}

\noindent The segments in $\Sigma$ are the different sets of nodes
representing CSP instances which are combined to form a MUSE
CSP. A solution to a MUSE CSP is defined to be a solution
to any one of its segments:

{\small \begin{definition}{\em (Solution to a MUSE CSP)}
A {\em solution} to a MUSE CSP is an assignment $\alpha$ to a
segment $\sigma=\{i_{1}, \ldots, i_{p}\}$ such that $\sigma \in
\Sigma$ and $\alpha \in L_{i_{1}} \times \cdots \times
L_{i_{p}}$ such that $R1(i_{x}, \alpha(i_{x}))$ holds for every node
$i_{x} \in \sigma$, and $R2(i_{x}, \alpha(i_{x}), i_{y},
\alpha(i_{y}))$ holds for every pair of nodes $i_{x}, i_{y} \in
\sigma$, such that $i_{x} \not = i_{y}$.
\end{definition}}

\noindent Depending on the application, the solution for a MUSE CSP could 
also be  the set of all consistent labels for a single path through
the MUSE CSP, a single set of labels for each of the paths (or CSPs),
or all compatible sets of labels for each of the paths.

%  Regardless of the choice of solution,
%it is desirable to prune the search space before selecting
%a solution by enforcing local consistency conditions, 
% such as node and arc consistency. 

A MUSE CSP can be solved with a modified backtracking algorithm
which finds a consistent label assignment for a segment.  However, 
when the constraints are sufficiently tight,
the search space can be pruned by enforcing local consistency conditions, such
as node, arc, and path consistency. To gain the efficiency
resulting from enforcing local consistency conditions before
backtracking, node, arc, and path consistency must be modified for
MUSE CSP.  The definitions for MUSE CSP node consistency, arc
consistency, and path consistency appear in Definitions 
\ref{muse_node_consistency_def}, \ref{muse_arc_consistency_def}, 
and \ref{muse_path_consistency_def}, respectively.


{\small \renewcommand{\baselinestretch}{.95}\begin{definition}{\em (MUSE Node Consistency)}
An instance of MUSE CSP is said to be {\em node consistent} if and
only if
each node's domain $L_{i}$ contains only labels for which 
the unary constraint $R{\it1}$ holds, i.e.: 
\[\forall i \in N : \forall a \in L_{i} : R{\it 1}(i,a)\]
\label{muse_node_consistency_def}
\end{definition}}
{\small \renewcommand{\baselinestretch}{.95}\begin{definition}{\em (MUSE Arc Consistency)}  
An instance of MUSE CSP is
said to be {\em MUSE arc consistent} if and only if for every label $a$ in
each domain $L_{i}$ there is at least one segment $\sigma$ whose
nodes' domains contain at least one label $b$ for which the binary
constraint $R{\it2}$ holds, i.e.:
\[\forall i \in N:
\forall a \in L_{i} : 
\exists \sigma \in \Sigma : i \in \sigma \wedge
\forall j \in \sigma : j \not = i \Rightarrow
\exists b \in L_{j} : R{\it 2}(i,a,j,b)\]
\label{muse_arc_consistency_def}
\end{definition}}
{\small \renewcommand{\baselinestretch}{.95} \begin{definition}{\em (MUSE Path Consistency)}  An instance of
MUSE CSP\
 is
said to be {\em path consistent} if and only if:\\ \\
$\forall i,j \in N: i \neq j \Rightarrow (\forall a \in L_{i}:  \forall b \in L_{j}:
\exists \sigma \in \Sigma: i,j \in \sigma \wedge \forall k \in \sigma:
k \neq i \wedge k \neq j \wedge Path(i,k,j) \Rightarrow\\
\hspace*{.5in} (R{\it 2}(i,a,j,b)$ $\Rightarrow \exists c \in L_{k}: R{\it 2}(i,a,k,c) \wedge  R{\it 2}(k,c,j,b)))$
\label{muse_path_consistency_def}
\end{definition}}
%\renewcommand{\baselinestretch}{1.5} 

A MUSE CSP is node consistent if all of its segments are node
consistent.  Unfortunately, MUSE CSP arc consistency requires more
attention.  When enforcing arc consistency in a CSP, a label $a \in
L_{i}$ can be eliminated from node $i$ whenever any other domain
$L_{j}$ has no labels which together with $a$ satisfy the binary
constraints.  However, in a MUSE CSP, before a label can be eliminated
from a node, it must be unsupported by the arcs of every segment in
which it appears, as required by the definition of MUSE arc
consistency shown in Definition \ref{muse_arc_consistency_def}.
Notice that Definition \ref{muse_arc_consistency_def} reduces to
Definition \ref{arc_consistency_def} when the number of segments is
one.


To demonstrate how MUSE arc consistency applies to a MUSE CSP,
consider the MUSE CSP in Figure \ref{example1}a.  Notice that label $c
\in L_{2}$ is not supported by any of the labels in $L_{3}$ and
$L_{4}$, but does receive support from the labels in $L_{1}$.  Should
this label be considered to be MUSE arc consistent?  The answer is no
because node $2$ is only a member of paths through the DAG which
contain node $3$ or node $4$, and neither of them support the label
$c$.  Because there is no segment such that all of its nodes have some
label which supports $c$, $c$ should be eliminated from $L_{2}$.  Once
$c$ is eliminated from $L_{2}$, $a$ will also be eliminated from
$L_{1}$.  This is because the elimination of $c$ from $L_{2}$ causes
$a$ to loose the support of node $2$.  Since node $2$ is a member of
every path, no other segment provides support for $a$.  The MUSE arc
consistent DAG is depicted in Figure \ref{example1}b.  Note that MUSE
arc consistency does not ensure that the individual segments are arc
consistent as CSPs.  
For example, Figure
\ref{example2} is MUSE arc consistent even though its segments
are not CSP arc consistent.  This is because $c$ receives arc support 
(which is a very local computation) from the arcs of at least one of
the paths.  We cannot ensure that the values that support a label are
themselves mutually consistent by considering MUSE arc consistency
alone.  For this case, MUSE path consistency together with MUSE arc
consistency would be needed to eliminate the illegal labels $c$ and $a$.
\begin{figure}
\centerline{\psfig{figure=example.ps,width=6.0in}}
\caption{a. A MUSE CSP before MUSE arc consistency is achieved; b. A MUSE CSP
after MUSE arc consistency is achieved.}
\label{example1}
\end{figure}
\begin{figure}
\centerline{\psfig{figure=example2.ps,width=3.0in}}
\caption{A MUSE CSP which is MUSE arc consistent, but not arc
consistent for each segment.}
\label{example2}
\end{figure}

	When enforcing path consistency in a CSP, $R{\it2}(i,a,j,b)$ 
becomes false if, for any third node $k$, there is no label
$c \in L_{k}$ such that $R{\it 2}(i,a,k,c)$ and $R{\it 2}(k,c,j,b)$
are true. In MUSE CSP, if a binary constraint becomes path inconsistent
in one segment, it could still be allowed in another.  Therefore, the
definition of MUSE path consistency is modified as shown in Definition
\ref{muse_path_consistency_def}.  

Enforcement of MUSE arc and path consistency requires modification of
the traditional CSP algorithms.  These algorithms will be described
after we introduce several applications for which MUSE CSP has proven
useful.

\section{MUSE CSP and Constraint-based Parsing}

It is desirable to represent a MUSE CSP as a directed acyclic
graph (DAG) where the directed paths through the DAG correspond to instances of
CSP problems.  It is often easy to determine which variables should be
shared and how to construct the DAG.  The application presented in this
section is one for which MUSE CSP is useful.
A parsing problem is naturally represented as a DAG because of the
presence of ambiguity.  In many cases, the same word can
have multiple parts of speech; it is convenient to represent
those words as  nodes in a MUSE CSP.  In speech recognition
systems, the identification of the correct words in a sentence
can be improved by using syntactic constraints.  However, a
word recognition algorithm often produces a lattice of word
candidates.  Clearly, individually parsing each of the
sentences in a lattice can be inefficient.

\subsection{Parsing with Constraint Dependency Grammar} 

Maruyama developed a new grammar called Constraint Dependency 
Grammar (CDG) \cite{maruyama,maruyama2,maruyama1}.
He then showed how CDG parsing can be cast as a CSP with a finite
domain, so constraints can be used to rule out ungrammatical sentences.  
A CDG is a four-tuple, 
$\langle \Sigma, R, L, C \rangle$, where:
\vskip .10in
\renewcommand{\baselinestretch}{.95}
{\small {\begin{tabular}{l}
{\bf{$\Sigma$}} = a finite set of preterminal symbols, or lexical
categories. \\
{\bf{$R$}} = a finite set of uniquely named roles (or role-ids) =
\{$r_{1},\ldots,r_{p}$\}. \\
{\bf{$L$}} = a finite set of labels = \{$l_{1},\ldots,l_{q}$\}. \\
{\bf{$C$}} = a finite set of constraints that an assignment {\bf{A}}
must satisfy. \\
\end{tabular}}}  
\vspace{.10in}
\renewcommand{\baselinestretch}{1.5}

\noindent 
A sentence $s = w_{1} w_{2} w_{3} \ldots w_{n}\in\Sigma^{*}$ is a string
of length $n$.  For each word $w_{i}\in\Sigma$ of a sentence $s$, we must keep
track of $p$ different roles (or variables).  A role is a variable which takes on
{\em role values\/} of the form $<$$l,m$$>$,
where $l \in L$ and $m \in \{nil, 1, 2, \ldots n\}$. Role values are
denoted in examples as {\em label-modifiee}.  In parsing,
each  label in $L$ indicates a different syntactic function.
The value of $m$ in the role value $<$$l,m$$>$, when assigned to a
particular role of $w_{i}$, specifies the position of the word that
$w_{i}$ is modifying when it takes on the function specified by the
label, $l$ (e.g., subj-3 indicates that the word with that label is
a subject when it modifies the third word in the sentence).  
The sentence $s$ is said to be {\em
generated} by the grammar $G$ if there exists an assignment {\bf A\/}
which maps a role value to each of the $n*p$ roles for $s$ such that
the constraint set $C$ (described in the next paragraph) is satisfied.
 
A {\em constraint set\/} is a logical formula of the
form:
$\forall x_{1}, x_{2}, \ldots, x_{a}
\mbox{ (and } \mbox{P$_{1}$ } \mbox{P$_{2}$ } \ldots \mbox{P$_{m}$)}$,
where each $x_{i}$ ranges over all of the role values in each of the roles
for each word of $s$. 
Each subformula P$_{i}$ in $C$ must be of the form: (if $Antecedent$ $Consequent$), 
where $Antecedent$ and $Consequent$ are
predicates or predicates joined by the logical connectives.
Below are the basic components used to express constraints.

{\small 
\begin{itemize}
\setlength{\itemsep}{-0.05in}
\item {\bf{Variables:}} $x_{1}$, $x_{2}$, $\ldots$ $x_{a}$ ($a=2$ in \cite{maruyama}).
\item {\bf{Constants:}} elements and subsets of $\Sigma$ $\cup$ $L$ $\cup$ $R$ $\cup$ 
\{nil, 1, 2, $\ldots$, $n$\}, where $n$ corresponds to the number of words in a sentence.  
\item {\bf{Functions:}}\\
{\bf{(pos x)}} returns the position of the word for role value $x$.\\
{\bf{(rid x)}} returns the role-id for role value $x$.\\
{\bf{(lab x)}} returns the label for role value $x$. \\
{\bf{(mod x)}} returns the position of the modifiee for role value $x$.\\
{\bf{(cat y)}} returns the category (i.e., the element in $\Sigma$)
for the word at position $y$.
\item {\bf{Predicates:}} $=$, $>$, $<$\begin{singlespace}\footnote{Note that 1 $>$ nil or
1 $<$ nil is false, because nil is not an integer.  For MUSE networks,
we relate position intervals using  $<$, $>$, and $=$.}\end{singlespace}.
\item {\bf{Logical Connectives:}} and, or, not.
\end{itemize}}

\noindent  A subformula P$_{i}$ is called a
{\em unary constraint\/} if it contains one variable and a {\em binary
constraint\/} if it contains two.  
A CDG grammar has two associated parameters,  {\em
degree\/} and {\em arity}. The degree of a grammar G is the number of roles.
The arity of the grammar, $a$, corresponds to the maximum number of
variables in the subformulas of $C$. 

Consider the example grammar, $G_{1}$, which is defined 
using the following four-tuple:
$\langle\Sigma_{1}=\{\mbox{det}, \mbox{noun}, \mbox{verb}\},
R_{1}=\{\mbox{governor}\}$, $L_{1}=\{\mbox{det}, \mbox{root},
\mbox{subj}\}$, $C_{1}$ (see constraints in $\mbox{Figure \ref{parsing})}
\rangle$.    $G_{1}$ has a degree of one and an arity of two.  To
illustrate the process of parsing with constraint satisfaction,
Figure \ref{parsing} shows the steps for parsing the sentence
{\em The dog eats}.  To simplify the presentation of this example, the
grammar uses a single role, the {\em governor\/} role, which is
denoted as {\bf G} in the constraint network in Figure \ref{parsing}.
The governor role indicates the function a word fills in a
sentence when it is governed by its head word.  A word is called the
head of a phrase when it forms the basis of the phrase (e.g.,
the verb is the head of the sentence).  In useful
grammars, we would also include several
needs roles (e.g, need1, need2) to make certain that a head word has
all of the constituents it needs to be complete (e.g., a singular
count noun needs a determiner to be a complete noun phrase). 
\begin{figure}[p]
\centerline{\psfig{figure=parsing.ps,height=8.3in}}
\caption{Using constraints to parse the sentence: {\em The dog eats}.}
\label{parsing}
\end{figure}
To determine whether the sentence, {\em The dog eats}, 
is generated by the grammar, the CDG
parser must be able to assign at least one role value to each of the $n * p$ roles  that satisfies
the grammar constraints ($n=3$ is
sentence length, and $p=1$ is the number of roles).  Because the 
values for a role are selected from the finite set $L_{1}$ {\large
$\times$} \{nil, 1, 2, 3\}, CDG parsing can be viewed as a
constraint satisfaction problem over a finite domain.  Therefore,
constraint satisfaction can be used to
determine the possible parses of this sentence.  

Initially, for each word, all possible role values are assigned to 
the governor role. We assume that
a word must either modify another word (other than itself) or 
modify no word ($m$=nil).  Nothing is gained in CDG by having a
word modify itself.   Next the unary constraints are applied to
all of the role values in the constraint network.  A role value is 
incompatible with
a unary constraint if and only if it satisfies the antecedent, but not the
consequent. Notice in Figure \ref{parsing} that all the role
values  associated with the governor role of the first word ({\em the})
satisfy the antecedent of the first unary
constraint, but det-nil, subj-nil, subj-2, subj-3, 
root-nil, root-2, and root-3 do not satisfy the consequent, and so they are incompatible
with the constraint.  When a role value violates a unary
constraint, node consistency eliminates those role values from their
role because they can never participate in a parse for the sentence.
After all unary constraints are applied to the
top constraint network in Figure \ref{parsing}, the second network is
produced.

Next, binary constraints are applied.  Binary constraints
determine which pairs of role values can legally coexist.  To keep
track of pairs of role values, {\em arcs\/} are constructed connecting each role to
all other roles in the network, and each arc has an
associated {\em arc matrix}, whose row and column indices are the role
values associated with the two roles it connects.  The entries in an
arc matrix can either be {\bf 1\/} (indicating that the two role
values indexing the entry are compatible) or {\bf 0} (indicating
that the role values cannot simultaneously exist).  Initially, all
entries in each matrix are set to {\bf 1}, indicating that the
pair of role values indexing the entry are initially compatible
(because no constraints have been applied). In our example, the single binary constraint
(shown in Figure \ref{parsing}) is applied to the pairs of role values
indexing the entries in the matrices.  For example, when x=det-3
for {\em the} and y=root-nil for {\em eats}, the consequent of the
binary constraint fails; hence, the role values are incompatible.
This is indicated by replacing the entry of {\bf 1\/} with {\bf 0}.

Following the binary constraints, the roles of the
constraint network can still contain role values which are
incompatible with the  parse for the sentence.   Role values that are
not supported by the binary constraints can be eliminated by 
achieving arc consistency. For example, det-3 for {\em the} is not supported by the
remaining role value  for {\em eats\/} and is thus deleted
from the role.  

After arc consistency, the example sentence has a
single parse because there is only one value per role in the
sentence.  A parse for a sentence consists of an assignment of role
values to roles such that the unary and binary constraints are
satisfied for that assignment.  In general, there can be more than one parse for a sentence; hence, there can
be more than one assignment of values to the roles of the sentence.  Note that the assignment for the
example sentence is:
\begin{center}\begin{tabular}{|c|c|c||c|}
\cline{1-4}
{\bf pos}  & {\bf word}  & {\bf cat} & {\bf governor role's value}\\ \hline
{\bf 1}     & the           & det       & det-2\\
{\bf 2}     & dog           & noun      & subj-3\\
{\bf 3}     & eats          & verb      & root-nil\\ \hline
\end{tabular}
\end{center}

If there is only one possible sentence such that the part of speech of
each of the words is known in advance, then the parsing problem
can be cast as a CSP.  However, for the ambiguity present in written
and spoken sentences to be handled uniformly requires the use of MUSE CSP.

\subsection{Processing Lexically Ambiguous Sentences with CDG}

One shortcoming of Maruyama's constraint-based parser is that it
requires a word to have a single part of speech; however, many words in the English
language have more than one lexical category.   This assumption
is captured in the way that Maruyama writes constraints involving
category information; the category is determined based on the position
of the word in the sentence.  However, even in our simple example, 
the word {\em dog\/} could have been either a noun or a verb prior to
the propagation of syntactic constraints.  Since parsing can be
used to lexically disambiguate the sentence, ideally, the parsing
algorithm should not require that the part of speech for the words be known prior to
parsing. 

%\begin{figure}
%\centerline{\psfig{figure=lex-amb.ps,height=5.5in}}
%\caption{Parsing the lexically ambiguous sentence: {\em The dog eats}.}
%\label{lex-amb}
%\end{figure}


Lexically ambiguous words can easily be accommodated by creating
a CSP for each possible combination of lexical categories; however,
this would be combinatorially explosive.  In contrast, using a MUSE
CSP, we can create a separate word node for each legal part of speech
of a word, sharing those words that are not ambiguous across all
segments. 
%(see Figure \ref{lex-amb}).  
Since position does not uniquely define the
category of a word, we must allow category
information to be accessed through the role value rather than the
position of the word in the sentence (i.e., use {\tt (cat x)} rather
than {\tt (cat (pos x))}).  Once we associate category information with a
role value, we could instead create role values for each lexical category
for a word and store all of the values in a single word node.
However, this representation is not as convenient as the MUSE CSP representation
for the problem.  In the lexically augmented CSP,
when there is more than one role per word (this is usually the case),
the role values associated with one lexical category for one role
cannot support the role values associated with another lexical
category in another role for the same word.  Additional
constraints must be propagated to enforce this requirement.
The MUSE CSP representation does not suffer from this problem.
By using a separate node for each part of speech, the 
MUSE CSP directly represents the independence of the alternative lexical
categories for a given word.  The space requirements for the arc
matrices in the MUSE representation is lower than for the
lexicalized CSP as there is no arc between the roles for the
different lexical categories for a word in the MUSE representation.
Note that MUSE arc consistency is equivalent to
performing arc consistency on the lexically augmented CSP (after the
additional constraints are propagated)\begin{singlespace}\footnote{As
a simple demonstration, consider merging nodes $3$ and $4$ from Figure
\ref{example2} into a single node such that the value $e$ and $f$ keep
track of the fact that they have type $3$ and $4$, respectively.
Under these circumstances, CSP arc consistency will give the same
results as MUSE CSP arc consistency; even though $a$ and $c$ appear in
no solutions, they are not eliminated.  Note that this example
uses only one role per node.}\end{singlespace}.  Most importantly, MUSE CSP can represent
lattices that cannot be combined into a single CSP.

The technique of creating separate nodes for
different instances of a word can also be used to handle feature analysis
(like number and person) in parsing
\cite{context-paper}.  Since some words have multiple feature values,
it is often more efficient to create a single node with a set of
feature values, apply syntactic constraints, and then split the node
into a set of nodes with a single feature value prior to applying
the constraints pertaining to the feature type. Node splitting
can also be used to support the use of context-specific constraints
\cite{context-paper}.  

\subsection{Lattice Example}

Much of the motivation for extending CSP comes from our work in
spoken language parsing \cite{speech-paper,icassp93,icslp}.
The output of a hidden-Markov-model-based speech recognizer can be
thought of as a lattice of word candidates.  Unfortunately, a lattice
contains many word candidates that can never appear in a sentence
covering the duration of a speech utterance.  By converting the
lattice to a word graph, many word candidates in the lattice can be
eliminated.  Figure
\ref{speech_example} depicts a word graph constructed from a simple
lattice.  Notice that the word {\em tour\/} can be eliminated when the
word graph is constructed.  In order to accommodate words that occur over time
intervals that may overlap, each word's position in the lattice is now
represented as a tuple $(b,e)$ such that $b<e$.  The positional relations defined
for constraints are easily modified to operate on tuples \cite{speech-paper}.
\begin{figure}
\centerline{\psfig{figure=speech_example.ps,height=2.9in}}
\caption{Multiple sentence hypotheses can be parsed simultaneously
by applying constraints over a word graph rather than individual
sentences extracted from a lattice.}
\label{speech_example}
\end{figure}

	After construction, the word graph often contains spurious sentence hypotheses
which can be pruned by using a variety of constraints (e.g., syntactic, semantic, etc.). 
We can apply constraints to individual sentences to rule out those that
are ungrammatical; however, individually processing
each sentence hypothesis is inefficient since many have a high degree
of similarity. If the spoken language parsing problem is structured as
a MUSE CSP problem, then the constraints used to parse individual
sentences would be applied to the word graph of sentence hypotheses,
eliminating from further consideration many hypotheses which are
ungrammatical.  

We have developed a MUSE CSP constraint-based parser, {\sc PARSEC}
\cite{speech-paper,context-paper,icassp93,icslp}, which is capable of
parsing  word graphs containing multiple sentences 
produced by a speech recognition module.  We have
developed syntactic and semantic constraints for parsing single
sentences, which when applied to a word graph, eliminate those
hypotheses that are syntactically or semantically incorrect.  
The MUSE CSP used by our parser can be thought of as a parse forest which
is pruned by using constraints.  By applying constraints
from a wide variety of knowledge sources, the parser prunes the composite structure of
many of the role values associated with a role, as well as word nodes
with no remaining role values.  Several experiments \cite{icassp93,icslp}
have considered how effective syntactic and semantic constraints are at pruning word nodes that
can appear in no sentence hypothesis.  For our
work in speech processing, the MUSE arc consistency algorithm is very
effective at pruning the role values from  the composite structure that can never appear in
a parse for a sentence (i.e., an individual CSP).
Constraints are usually tight enough that MUSE arc consistency
eliminates role values that do not participate in at least one parse
for the represented sentences.


MUSE CSP is a useful way to process multiple sentences because the arc consistency
algorithm is effective at eliminating role values that cannot appear in sentence
parses.  Several factors contribute to the effectiveness of the arc consistency algorithm 
for this problem. First, the syntactic constraints
are fairly tight constraints.  Second,
the role values contain some segmental information that constrain the problem.  
Consider the word
graph in Figure \ref{not-applicable}.  The value s-(3,4) 
associated with the role marked {\bf N} for the word {\em are}
cannot support any of the values
for the role marked {\bf G} for the word {\em dogs} at position (3,5), 
because it is not legal in a segment
involving position (3,5).  In the figure, we mark those entries
where a value associated with one role is segmentally incompatible
with the values of another with an N.  These entries are
equivalent to 0.  Third, many times constraints
create symmetric dependencies between words in the sentence.  For example, one
constraint might indicate that a verb needs a subject to its left,
and another that a subject must be governed by a verb to its right.
\begin{figure}
\centerline{\psfig{figure=segmentlabel.ps,width=5.5in}}
\caption{In parsing word graphs, some of the values assigned to roles contain
segmental information which make them incompatible with the values
associated with some of the  other roles. For example, s-(3,4) cannot support any of the
values associated with the {\bf G} or {\bf N} roles of the word {\em dogs}.}
\label{not-applicable}
\end{figure}

\subsection{A Demonstration of the Utility of MUSE CSP Parsing}

To demonstrate the utility of MUSE CSP for simultaneously parsing
multiple CSP instances, consider the problem of determining which
strings of length $3n$ consisting of $a$'s, $b$'s, and $c$'s are in the
language $a^{n}b^{n}c^{n}$. For the value of $n=3$, this
problem can be represented as the single MUSE CSP problem shown in
Figure \ref{capture} (the roles and role values are not depicted
to simplify the figure).
We have devised constraints for this language (see Figure \ref{G2})
which eliminate all role values for all sentences not in the language
as well as all ungrammatical role values for a sentence in the language.
When these constraints are applied followed by MUSE arc
consistency to a lattice like that in Figure
\ref{capture} with a length divisible by three, then only the grammatical 
sentence will remain with a single parse.  For lattices containing only 
sentences with lengths that are not divisible by three, all role values are 
eliminated by MUSE arc consistency (there is no grammatical sentence).
Hence, there is no search required to extract a parse if there is one.
For the $n=3$ case of Figure \ref{capture}, the parse appears in Figure \ref{parse4}.
A single parse will result regardless of the $n$ chosen.
Note that the modifiees for the role values in the parse are used to ensure that
for each $a$, there is a corresponding $c$; for each $b$, there is a
corresponding $a$; and for each $c$, there is a  corresponding $b$.
Figure \ref{anbncn-results} examines the time needed to extract a
parse for sentences in the language $a^{n}b^{n}c^{n}$ from MUSE CSPs
representing all strings of length 3$n$, $1 \leq n \leq 7$, containing $a$, $b$, and $c$.
The time to perform MUSE AC-1 and extract the solution is compared to
the time to extract the solution without any preprocessing.
The time to perform MUSE AC-1 and extract the parse is stable as sentence length 
grows, but the time to extract a parse grows quickly for sentence lengths greater than 15 
when MUSE arc consistency is not used.
\begin{figure}
\centerline{\psfig{figure=anbncn2.ps,width=6.5in}}
\caption{A single MUSE CSP can simultaneously test all possible orderings of
$a$'s, $b$'s, and $c$'s for membership in the language
$a^{n}b^{n}c^{n}$, $n=3$.}
\label{capture}
\end{figure}
\begin{figure}\footnotesize\normalsize\renewcommand{\baselinestretch}{.85}\footnotesize
\renewcommand{\baselinestretch}{.85}
\begin{constraint}
{\bf{$\Sigma_{2}$}} = \{a, b, c\}
{\bf{$R_{2}$}} = \{governor\}
{\bf{$L_{2}$}} = \{a, b, c\}
{\bf{$C_{2}$}} = see below:
\end{constraint}
\begin{verbatim}
                         ; 3 Unary Constraints

(if (and (= (cat x) a)                     (if (and (= (cat x) b)
         (= (rid x) governor))                      (= (rid x) governor))
    (and (= (lab x) a)                         (and (= (lab x) b)
         (> (mod x) (pos x))))                      (< (mod x) (pos x))))

(if (and (= (cat x) c)
         (= (rid x) governor)) 
    (and (= (lab x) c)
         (< (mod x) (pos x))))

                         ; 8 Binary Constraints

(if (and (= (lab x) a)                     (if (and (= (lab x) b)
         (or (= (lab y) b)                          (= (lab y) c))
             (= (lab y) c)))                   (< (pos x) (pos y)))
    (< (pos x) (pos y)))	       

(if (and (= (lab x) a)                     (if (and (= (lab x) a) 
         (= (lab y) a)                              (= (mod x) (pos y))
         (> (pos x) (pos y)))                       (= (rid y) governor))
    (< (mod x) (mod y)))                       (= (lab y) c))

(if (and (= (lab x) b)                     (if (and (= (lab x) b)
         (= (lab y) b)                              (= (mod x) (pos y))
         (> (pos x) (pos y)))                       (= (rid y) governor))
    (< (mod x) (mod y)))                        (= (lab y) a))

(if (and (= (lab x) c)                     (if (and (= (lab x) c)
         (= (lab y) c)                              (= (mod x) (pos y))
         (> (pos x) (pos y)))                       (= (rid y) governor))
    (< (mod x) (mod y)))                       (= (lab y) b))

\end{verbatim}
\caption{ $G_{2}$ = $\langle \Sigma_{2},  R_{2}, L_{2}, C_{2} \rangle$  accepts the language $a^{n}b^{n}c^{n}$, n $\geq$ 0.}
\label{G2}
\end{figure}
\begin{figure}
\begin{center}\begin{tabular}{|c|c||c|}
\cline{1-3}\
{\bf pos}  & {\bf cat}  & {\bf governor role's value}\\ \hline
{\bf (1,2)}     & a         & a-(9,10)\\
{\bf (2,3)}     & a         & a-(8,9)\\
{\bf (3,4)}     & a         & a-(7,8)\\ \hline
{\bf (4,5)}     & b         & b-(3,4)\\
{\bf (5,6)}     & b         & b-(2,3)\\
{\bf (6,7)}     & b         & b-(1,2)\\ \hline
{\bf (7,8)}     & c         & c-(6,7)\\
{\bf (8,9)}     & c         & c-(5,6)\\
{\bf (9,10)}    & c         & c-(4,5)\\ \hline
\end{tabular}
\end{center}
\caption{The single parse remaining in the network depicted in
Figure 9 after the applying the constraints in $G_2$ and enforcing
MUSE arc consistency.}
\label{parse4}
\end{figure}
\begin{figure}
\centerline{\psfig{figure=anbncn-results2.ps,height=3in}}
\caption{This graph depicts the time to extract the parse 
for the language $a^{n}b^{n}c^{n}$ from a MUSE CSP representing all
sentences of length 3$n$, where $n$ varies from 1 to 7.  The
time to extract the parse without MUSE arc consistency is compared
to the time to perform MUSE AC-1 and extract the parse.  }
\label{anbncn-results}
\end{figure}

	The previous example involves a grammar where there can only
be one parse for a single sentence in the lattice; however, it
is a simple matter to provide similar
demonstrations for more complex cases.  For example,
the constraint grammar shown in Figure \ref{G3} can be 
to parse all possible sentences of a given length in the the language
$ww$, such that $w$ is in $\{a,b,c\}^+$.  Consider the
MUSE CSP in Figure \ref{capture2} (the roles and role values are
not depicted to simplify the figure).  After applying the constraints and
performing MUSE arc consistency on this MUSE CSP,
there are precisely 81 strings that are in $ww$,  and their
parses are compactly represented in the constraint network.  The
constraints plus MUSE arc consistency eliminate every
value that cannot appear in a parse.  For lattices containing
odd length sentences, no role values remain after MUSE arc consistency.
Figure \ref{ww-results} shows the time needed to extract all of the
parses for sentences in the language $ww$ from the MUSE CSPs as
we vary the length of $w$ from 1 to 8.
The time to perform MUSE AC-1 and extract the parses grows 
slowly as sentence length increases because the number of parses
increases with sentence length; however, it grows
more slowly than the time to extract the parses
when MUSE arc consistency is not used. 
\begin{figure}\footnotesize\normalsize\renewcommand{\baselinestretch}{.85}\footnotesize
\renewcommand{\baselinestretch}{.85}
\begin{constraint}
{\bf{$\Sigma_{3}$}} = \{a, b, c\}
{\bf{$R_{3}$}} = \{governor\}
{\bf{$L_{3}$}} = \{w1, w2\}
{\bf{$C_{3}$}} = see below:
\end{constraint}
\begin{verbatim}
                         ; 2 Unary Constraints

(if (= (lab x) w1)                        (if (= (lab x) w2)
    (< (pos x) (mod y)))                      (> (pos x) (mod y)))

                         ; 6 Binary Constraints

(if (and (= (lab x) w1)                  (if (and (= (lab x) w1)
         (= (lab y) w2))                          (= (lab y) w2))
    (< (pos x) (pos y)))                     (> (mod x) (mod y)))
       
(if (and (= (lab x) w1)                     (if (and (= (lab x) w2)
         (= (lab y) w1)                              (= (lab y) w2)
         (> (pos x) (pos y)))                        (> (pos x) (pos y)))
    (> (mod x) (mod y)))                      (< (mod x) (mod y)))

(if (and (= (lab x) w1)                   (if (and (= (lab x) w2)
         (= (mod x) (pos y)))                      (= (mod x) (pos y)))
    (and (= (lab y) w2)                       (= (lab y) w1))
         (= (cat x) (cat y))))

\end{verbatim}
\caption{ $G_{3}$ = $\langle \Sigma_{3},  R_{3}, L_{3}, C_{3} \rangle$  accepts the language $ww$.}
\label{G3}
\end{figure}
\begin{figure}
\centerline{\psfig{figure=ww.ps,width=6in}}
\caption{A single MUSE CSP can simultaneously test all possible orderings of
$a$'s, $b$'s, and $c$'s for membership in the language  $ww$ where $|w|=4$ .}
\label{capture2}
\end{figure}
\begin{figure}
\centerline{\psfig{figure=ww-results2.ps,height=3in}}
\caption{This graph depicts the time to extract all parses
for the language $ww$ from a MUSE CSP representing all
sentences of length 2 to 16 such that $w \in \{a, b, c\}^{+}$.  The
time to extract all parses without MUSE arc consistency is compared
to the time to perform MUSE AC-1 and extract all parses.  }
\label{ww-results}
\end{figure}

	Similar results have also been obtained with grammars used to parse
word graphs constructed from spoken sentences in the resource
management and ATIS domains \cite{icassp93,icslp,speech-paper}.



\section{The MUSE CSP Arc Consistency Algorithm}

    In this section, we introduce an algorithm, MUSE AC-1, to achieve MUSE CSP arc
consistency.  Because our algorithm builds upon the AC-4 algorithm
\cite{ac4paper}, we present that
algorithm first for comparison purposes.

\subsection{CSP Arc Consistency: AC-4}

AC-4 builds and maintains several data structures, described in
Figure \ref{notation_csp}, to allow it to efficiently achieve arc
consistency in a CSP.  Note that we have modified the notation
slightly to eliminate subscripts (which become quite cumbersome for
the path consistency algorithm).  Figure \ref{preprocess_csp} shows
the code for initializing the data structures, and Figure
\ref{csp_arc_algorithm} contains the algorithm for eliminating
inconsistent labels from the domains.  This algorithm requires
$\Theta(el^{2}$) time, where $e$ is the number of constraint arcs, 
and $l$ is the domain size \cite{ac4paper}.
\begin{figure}
\tabcolsep .05in
\renewcommand{\baselinestretch}{.85}
\tabcolsep .05in

\centerline{\small
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c} {\bf \ \ \ Notation\ \ \ } & 
\multicolumn{1}{|c|} {\bf Meaning
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}
} \\
\hline
\hline
$(i,j)$ &
\begin{tabular}{l}
An ordered pair of nodes.
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$E$ &
\begin{tabular}{l}
All node pairs $(i,j)$.  If $(i,j)\in E$, then  $(j,i)\in E$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$(i, a)$ & 
\begin{tabular}{l}
An ordered pair of node $i$ and label $a \in L_{i}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$L_{i}$ &
\begin{tabular}{l}
$\{a | a \in L$ and $(i,a)$ is permitted by the constraints (i.e., admissible)$\}$
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$R{\it 2}(i,a,j,b)$ &
\begin{tabular}{l}
$R{\it 2}(i,a,j,b) = 1$ indicates the admissibility $a \in L_i$ and $b \in L_j$ given\\
binary constraints. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Counter$[(i,j), a]$ & 
\begin{tabular}{l}
The number of labels in $L_{j}$ which are compatible with $a \in L_{i}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$S[i,a]$ & 
\begin{tabular}{l}
$(j,b) \in S[i,a]$ means that $a \in L_{i}$ and $b \in L_{j}$ are
simultaneously\\
admissible. This implies that $a$ supports $b$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$M[i,a]$ & 
\begin{tabular}{l}
$M[i,a]=1$ indicates that the label $a$ is not admissible for (and \\
has already been eliminated from) node $i$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$List$ &
\begin{tabular}{l}
A queue of arc support to be deleted. 
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}\\
\hline
\end{tabular}
}
\caption{Data structures and notation for the arc consistency algorithm, AC-4.}
\label{notation_csp}
\end{figure}

	In AC-4, if the label $a \in L_{i}$ is compatible with $b \in
L_{j}$, then $a$ {\em supports} $b$ (and vice versa).  To keep track
of how much support each label $a$ has, the number of labels in
$L_{j}$ which are compatible with $a$ in $L_{i}$ are counted and the
total stored in Counter$[(i,j), a]$ by the algorithm in Figure
\ref{preprocess_csp}.  If any Counter$[(i,j), a]$ is zero, then $a$ is
removed from $L_{i}$ (because it cannot appear in any solution), the
ordered pair $(i,a)$ is placed on the $List$, and M$[i,a]$ is set to 1 (to
avoid removing the element $a$ from $L_{i}$ more than once).  The
algorithm must also keep track of which labels that label $a$ supports
by using S$[i, a]$, a set of arc and label pairs.  For example, S$[i,
a] = \{ (j, b), (j, c) \} $ means that $a$ in $L_{i}$ supports $b$ and
$c$ in $L_{j}$.  If $a$ is ever removed from $L_{i}$, then $b$ and $c$
will loose some of their support.

After the preprocessing step in Figure \ref{preprocess_csp}, the
algorithm in Figure \ref{csp_arc_algorithm} loops until $List$ becomes
empty, at which point the CSP is arc consistent.  When $(i,a)$ is
popped off $List$ by this procedure, for each element $(j,b)$ in
S$[i,a]$, Counter$[(j,i), b]$ is decremented.  If Counter$[(j,i), b]$
becomes zero, $b$ would be removed from $L_{j}$, $(j,b)$ placed on
$List$, and M$[j,b]$ set to 1.
\begin{figure}
\initlct
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{5in}
\begin{tabbing}
\lct   \hspace{.05in} \=$List := \phi$;\\
\lct  \> {\bf for }\= $i \in N$ {\bf do} \\
\lct \> \> {\bf for} \=  $a \in L_{i}$ {\bf do} {\bf $\{$ }\\
\lct \> \> \> $S[i, a] := \phi$; \\
\lct \> \> \> $M[i, a] := 0$; {\bf $\}$ }\\
\lct \>  {\bf for} \= $(i,j) \in E$ {\bf do} \\
\lct \> \> {\bf for} \= $a \in L_{i}$ {\bf do} {\bf $\{$ }\\
\lct \> \> \> Total := 0; \\
\lct \> \> \> {\bf for} \= $b \in L_{j}$ {\bf do} \\
\lct \> \> \> \> {\bf if} \= $R{\it 2}(i,a,j,b)$ {\bf then} {\bf $\{$ }\\
\lct \> \> \> \> \> Total := Total+1; \\
\lct \> \> \> \> \> $S[j,b] := S[j,b] \cup \{(i,a)\}$; {\bf $\}$ }\\
\lct \> \> \> {\bf if} \= Total = 0 {\bf then} {\bf $\{$ }\\
\lct \> \> \> \> $L_{i} := L_{i} - \{a\};$ \\
\lct \> \> \> \> $List := List \cup \{(i, a)\}$; \\
\lct \> \> \> \> $M[i,a] := 1;$  {\bf $\}$ }\\
\lct \> \> \> $\mbox{Counter}[(i,j), a]$ := Total;  {\bf $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}}
\caption{Initialization of the data structures for AC-4.}
\label{preprocess_csp}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{5.5in}
\begin{tabbing}
\initlct
\lct  \hspace{.05in} \={\bf while} \= $List \not = \phi$ {\bf do} {\bf $\{$ }\\
\lct  \> \> pop $(i,a)$ from $List$; \\
\lct  \> \> {\bf for} \= $(j,b) \in S[i,a]$ {\bf do} {\bf $\{$ }\\
\lct \> \> \> Counter$[(j,i), b]$ := Counter$[(j,i), b] - 1;$ \\
\lct \> \> \> {\bf if} \= Counter$[(j,i), b]=0 \wedge M[j,b]=0$ {\bf
then} {\bf $\{$ }\\
\lct \> \> \> \> $L_{j} := L_{j}-\{b\}$; \\
\lct \> \> \> \> $List := List \cup \{(j, b)\}$; \\
\lct \> \> \> \> $M[j,b]$ := 1; {\bf $\}$ $\}$ $\}$ }
\end{tabbing}
\end{minipage} \\
\ \ \\
\hline
\end{tabular}
}
\caption{Eliminating inconsistent labels from the domains in AC-4.}
\label{csp_arc_algorithm}
\end{figure}

     Next, we describe the MUSE arc consistency algorithm for a MUSE CSP,
called MUSE AC-1.  We purposely keep our notation and presentation of
MUSE AC-1 as close as possible to that of AC-4 so that the reader can
benefit from the similarity of the two algorithms.

\subsection{MUSE AC-1}

MUSE arc consistency is enforced by removing those labels in each
$L_{i}$ which violate the conditions of Definition
\ref{muse_arc_consistency_def}.  MUSE AC-1 builds and maintains
several data structures, described in Figure \ref{notation}, to allow
it to efficiently perform this operation.  Many of these data
structures are borrowed from AC-4, while others exploit the DAG
representation of the MUSE CSP to determine when values are
incompatible in all of the segments.  Figure \ref{preprocess} shows the
code for initializing the data structures, and Figures
\ref{muse_csp_arc_algorithm} and \ref{update_dag} contain 
the algorithm for eliminating inconsistent labels from the domains.
\begin{figure}
\tabcolsep .05in
\renewcommand{\baselinestretch}{.85}

\centerline{\footnotesize
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c} {\bf \ \ \ Notation\ \ \ } & 
\multicolumn{1}{|c|} {\bf Meaning
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}
} \\
\hline
\hline
$(i,j)$ &
\begin{tabular}{l}
An ordered pair of nodes.
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$E$ &
\begin{tabular}{l}
All node pairs $(i,j)$ such that there exists a path of directed edges in $G$ \\
between $i$ and $j$. If $(i,j) \in E$, then $(j,i) \in E$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$(i, a)$ & 
\begin{tabular}{l}
An ordered pair of node $i$ and label $a \in L_{i}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$[(i,j), a]$ & 
\begin{tabular}{l}
An ordered pair of a node pair $(i,j)$ and a label $a \in L_{i}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$L_{i}$ &
\begin{tabular}{l}
$\{a | a \in L$ and $(i,a)$ is permitted by the constraints (i.e., admissible)$\}$
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$R{\it 2}(i,a,j,b)$ &
\begin{tabular}{l}
$R{\it 2}(i,a,j,b) = 1$ indicates the admissibility of $a \in L_i$ and $b \in L_j$ given\\
binary constraints. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Counter$[(i,j), a]$ & 
\begin{tabular}{l}
The number of labels in $L_{j}$ which are compatible with $a \in L_{i}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
S$[(i,j), a]$ & 
\begin{tabular}{l}
$(j,b) \in S[(i,j), a]$ means that $a \in L_{i}$ and $b \in L_{j}$ are
simultaneously\\
admissible. This implies that $a$ supports $b$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
M$[(i,j),a]$ & 
\begin{tabular}{l}
M$[(i,j),a]=1$ indicates that the label $a$ is not admissible for (and\\
has already been eliminated from) all segments containing $i$ and $j$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$List$ &
\begin{tabular}{l}
A queue of arc support to be deleted. 
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}\\
\hline
$G$ &
\begin{tabular}{l}
$G$ is the set of node pairs $(i,j)$ such that there exists a directed\\
edge from $i$ to $j$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Next-Edge$_{i}$ & 
\begin{tabular}{l}
Next-Edge$_{i}$ contains all node pairs $(i,j)$ such that there exists
a\\ 
directed edge $(i,j) \in G$.  It also contains $(i, {\rm end})$ if
$i$ is the last node\\ 
in a segment.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Prev-Edge$_{i}$ &
\begin{tabular}{l}
Prev-Edge$_{i}$ contains all node pairs $(j,i)$ such that there exists
a \\ 
directed edge $(j,i) \in G$.  It also contains $({\rm start},i)$ if
$i$ is the first node\\
in a segment.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Local-Prev-Support$(i,a)$ \ \ & 
\begin{tabular}{l}
A set of elements $(i,j)$ such that $(j,i)\in$ Prev-Edge$_{i}$, and if
$j \neq {\rm start}$,\\
$a$ must be compatible with at least one of $j$'s labels.  If\\
Local-Prev-Support$(i,a)$ becomes empty, $a$ in $i$ is no
longer admissible.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Local-Next-Support$(i,a)$ \ \ &
\begin{tabular}{l}
A set of elements $(i,j)$ such that $(i,j) \in$ Next-Edge$_{i}$, and
if $j \neq {\rm end}$,\\
$a$ must be compatible with at least one of $j$'s labels. If \\
Local-Next-Support$(i,a)$ becomes empty, $a$ in $i$ is no
longer admissible.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Prev-Support$[(i,j), a]$ &
\begin{tabular}{l}
$(i,k) \in$ Prev-Support$[(i,j), a]$ implies that $(k,j) \in$ Prev-Edge$_{j}$, and\\
if $k \neq {\rm start}$, then $a \in L_{i}$ is compatible with at least one
of $j$'s and\\ 
one of $k$'s labels. If Prev-Support$[(i,j), a]$ becomes empty, then
$a$ is \\
no longer admissible in segments containing $i$ and $j$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Next-Support$[(i,j), a]$ &
\begin{tabular}{l}
$(i,k) \in$ Next-Support$[(i,j), a]$ implies that $(j,k) \in$ Next-Edge$_{j}$, and\\
if $k \neq {\rm end}$, then $a \in L_{i}$ is compatible with at least one
of $j$'s and\\ 
one of $k$'s labels. If Next-Support$[(i,j), a]$ becomes empty, then $a$ is\\
no longer admissible in segments containing $i$ and $j$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\end{tabular}
}

\caption{Data structures and notation for MUSE AC-1.}
\label{notation}
\end{figure}

%\renewcommand{\baselinestretch}{1.5}
     In MUSE AC-1 as in AC-4, if label $a$ at node $i$ is compatible with label $b$ at node
$j$, then $a$ {\em supports} $b$.  To keep track of how much
support each label $a$ has, the number of labels in $L_{j}$ which are
compatible with $a$ in $L_{i}$ are counted, and the total is stored in
Counter$[(i,j), a]$.   For CSP arc consistency, if  Counter$[(i,j),
a]$ is zero, $a$ would be immediately removed from $L_{i}$,
because that would mean that $a$ could never appear in any solution.
However, in MUSE arc consistency, this may not be the case, because
even though $a$ does not participate in a solution for any of the
segments which contain $i$ and $j$, there could be another segment for which
$a$ would be perfectly legal.  A label cannot become globally
inadmissible until it is incompatible with every segment.
Hence, in MUSE CSP, if Counter$[(i,j), a]$ is zero, the algorithm
simply places $[(i,j),a]$ on $List$ and records that fact by setting
M$[(i,j),a]$ to 1.  By placing $[(i,j),a]$ on $List$, the
algorithm is indicating that the segments containing $i$ and $j$ do
not support the label $a$. 

MUSE AC-1 must also keep track of those labels in $j$ that label $a$
in $L_{i}$ supports by using
S$[(i,j), a]$, a set of node-label pairs. 
For example,  S$[(i,j), a] = \{ (j, b), (j,c) \} $ means that $a$ in
$L_{i}$ supports $b$ and $c$ in $L_{j}$.  If $a$ is ever invalid for
$L_{i}$, then $b$ and $c$ will loose some of their support. 

Because $\Sigma$ is a DAG, MUSE AC-1 is able to use the
properties of the DAG to identify local (and hence efficiently
computable) conditions under which labels become globally
inadmissible.  Segments are defined as  paths through the
MUSE CSP from {\rm start} to {\rm end}.  If a value associated
with a variable is not supported by any of the variables which precede it
or follow it, then there is no way that the value can be used by
any segment, so it can be deleted by the arc consistency algorithm.
In addition, if a value in a variable's domain is supported by the constraints for 
values associated with a second variable, but the second variable is preceded or
followed by variables that have no values supporting the value, then because a solution
involves a path of variables in the MUSE DAG, the value cannot be supported for any segment
involving the two variables.  These two ideas provide the
basis for the remaining data structures used by MUSE AC-1.


Consider Figure \ref{local_dag}, which shows the nodes
which are adjacent to node $i$ in the DAG.  Because
every segment in the DAG which contains node $i$ is
represented as a directed path in the DAG going through node $i$,
either node $j$ or node $k$ must be in every segment containing $i$.  
Hence, if the
label $a$ is to remain in $L_{i}$, it must be compatible with at least
one label in either $L_{j}$ or $L_{k}$.
Also, because either $n$ or $m$ must be contained in every segment
containing $i$, if label $a$ is to remain in $L_{i}$, it must also be
compatible with at least one label in either $L_{n}$ or $L_{m}$.


In order to track this
dependency, two sets are maintained for each label $a$ at node $i$,
Local-Next-Support$(i,a)$ and Local-Prev-Support$(i,a)$.
Local-Next-Support$(i,a)$ is a set of ordered node pairs $(i,j)$ such
that $(i,j) \in$ Next-Edge$_{i}$, and if $(i,j) \in E$, there is at least one label $b
\in L_{j}$ which is compatible with $a$.  Local-Prev-Support$(i,a)$ is
a set of ordered pairs $(i,j)$ such that $(j,i) \in$ Prev-Edge$_{i}$,
and if $(i,j) \in E$,
there is at least one label $b \in L_{j}$ which is compatible with
$a$.  Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when $({\rm start},i) \in$ Prev-Edge$_{i}$, $(i,{\rm start})$ is  added to
Local-Prev-Support$(i,a)$, and when $(i,{\rm end}) \in$ Next-Edge$_{i}$,
$(i,{\rm end})$ is added to Local-Next-Support$(i,a)$.  This is to
prevent a label from being ruled out because no nodes precede or 
follow it in the DAG.  Whenever one of $i$'s adjacent nodes, $j$, no 
longer has any labels $b$ in its domain which are compatible with $a$,
then $(i,j)$ should be removed from  Local-Prev-Support$(i,a)$ or
Local-Next-Support$(i,a)$, depending on whether the edge is from $j$
to $i$ or from $i$ to $j$, respectively.  If either
Local-Prev-Support$(i,a)$ or Local-Next-Support$(i,a)$ becomes 
empty, then $a$ is no longer a part of any MUSE arc consistent instance, and should be
eliminated from $L_{i}$.  In Figure \ref{local_dag}, the label
$a$ is admissible for the segments containing both $i$ and $j$, but not for
the segments containing $i$ and $k$.  If because of constraints, the labels in $j$ become
inconsistent with $a$ on $i$, $(i,j)$ would
be eliminated from Local-Next-Support$(a,i)$, leaving an empty set.
In that case, $a$ would no longer be supported by any segment.
\begin{figure}
\centerline{\psfig{figure=local_dag.ps,height=1.8in}}
\caption{Local-Prev-Support and Local-Next-Support for an example DAG.  The
sets indicate that the label $a$ is allowed for every segment which contains
$n$, $m$, and $j$, but is disallowed for every segment which contains
$k$. The solid directed lines are members of $G$, and the solid
undirected lines represent members of $E$.}
\label{local_dag}
\end{figure}

The algorithm can utilize similar conditions for nodes which are not 
directly connected to $i$ by Next-Edge$_{i}$ or Prev-Edge$_{i}$.  
Consider Figure \ref{far_dag}. Suppose that the label
$a$ at node $i$ is compatible with a label in  $L_{j}$, but it is incompatible
with the labels in $L_{x}$ and $L_{y}$, then
it is reasonable to eliminate $a$ for all segments containing 
both $i$ and $j$, because those segments would have to
include either node $x$ or $y$.   To determine whether a
label is admissible for a set of segments containing $i$ and $j$,
we calculate Prev-Support$[(i,j),a]$ and Next-Support$[(i,j),a]$
sets. Next-Support$[(i,j),a]$  includes all $(i,k)$ arcs which support $a$ in
$i$ given that there is a directed edge from $j$ to $k$, and
$(i,j)$ supports $a$. Prev-Support$[(i,j),a]$  includes all $(i,k)$ arcs which support $a$ in
$i$ given that there is a directed edge from $k$ to $j$, and
$(i,j)$ supports $a$. 
Note that Prev-Support$[(i,j),a]$ will  contain an 
ordered pair $(i,j)$ if $(i,j) \in$ Prev-Edge$_{j}$, and
Next-Support$[(i,j),a]$ will contain an
ordered pair $(i,j)$ if $(j,i) \in$ Next-Edge$_{j}$.  These elements
are included because the edge between nodes $i$ and $j$
is sufficient to allow $j$'s labels to support $a$ in the segment
containing $i$ and $j$.  Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when $({\rm start},j) \in$ Prev-Edge$_{j}$, $(i,{\rm start})$ is  added to
Prev-Support$[(i,j),a]$, and when $(j,{\rm end}) \in$ Next-Edge$_{j}$,
$(i,{\rm end})$ is added to Next-Support$[(i,j),a]$.  This is to
prevent a label from being ruled out because no nodes precede or follow it in the
DAG. 

Figure \ref{preprocess} shows the Prev-Support, Next-Support,
Local-Next-Support, and Local-Prev-Support sets that the initialization
algorithm creates  for a simple example DAG.
After the initialization step, these sets contain all node pairs that are allowed based
on the connectivity of $G$.  Later, during the consistency step those
node pairs which do not support the associated label are eliminated from each set.
\begin{figure}
\centerline{\psfig{figure=far_dag.ps,width=2.8in}}
\caption{If $\mbox{Next-Edge}_{j}=\{(j,x),(j,y)\}, \mbox{Counter}[(i,x),a]=0$, and $\mbox{Counter}[(i,y),a] = 0$, then $a$ is inadmissible for every segment containing both $i$ and $j$. The solid directed lines are members of $G$, and the solid undirected lines represent members of $E$.}
\label{far_dag}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
\initlct
\lct  \hspace{.05in} \=$List := \phi$;\\
\lct  \> $E := \{(i,j) | \exists \sigma \in \Sigma : i,j \in \sigma \wedge i \not =
j \wedge i,j \in N\}$; \\
\lct \> {\bf for }\= $(i,j) \in E$ {\bf do} \\
\lct \> \> {\bf for} \=  $a \in L_{i}$ {\bf do} {\bf $\{$ }\\
\lct \> \> \>  S$[(i,j), a] := \phi$; \\
\lct \> \> \>  M$[(i,j), a] := 0$; \\
\lct \> \> \>  Local-Prev-Support$(i,a) := \phi$; Local-Next-Support$(i,a) := \phi$; \\
\lct \> \> \> Prev-Support$[(i,j), a] := \phi$; Next-Support$[(i,j), a] := \phi$; {\bf $\}$ }\\
\lct \> {\bf for }\= $(i,j) \in E$ {\bf do} \\
\lct \> \> {\bf for} \=  $a \in L_{i}$ {\bf do} {\bf $\{$ }\\
\lct \> \> \> Total := 0; \\
\lct \> \> \> {\bf for} \= $b \in L_{j}$ {\bf do} \\
\lct \> \> \> \> {\bf if} \=$R{\it 2}(i,a,j,b)$ {\bf then} {\bf $\{$ }\\
\lct \> \> \> \> \> Total := Total+1; \\
\lct \> \> \> \> \> S$[(j,i), b] := $ \= S$[(j,i), b]$ $\cup$ $\{(i,a)\}$; {\bf $\}$ }\\
\lct \> \> \> {\bf if} \=Total=0 {\bf then} {\bf $\{$ }\\
\lctl{init-list} \> \> \> \> $List := List \cup \{[(i,j), a]\}$;\\
\lct \> \> \> \> M$[(i,j), a] := 1$; {\bf $\}$ }\\
\lct \> \> \> Counter$[(i,j), a]$ := Total; \\
\lct  \> \> \> Prev-Support$[(i,j), a]$ := \=$\{ (i,x) | (i,x) \in E \wedge (x,j) \in \mbox{Prev-Edge}_{j} \} $ \\
\> \> \> \> $\cup$ $\{(i,j) | (i,j) \in \mbox{Prev-Edge}_{j} \}$ \\
\> \> \> \> $\cup$ $\{(i,\mbox{\rm start}) | (\mbox{\rm start},j) \in \mbox{Prev-Edge}_{j}\}$; \\ 
\lct \> \> \> Next-Support$[(i,j), a]$ := \=$\{(i,x) | (i,x) \in E \wedge (j,x) \in \mbox{Next-Edge}_{j}\}$\\
\> \> \> \> $\cup$ $\{(i,j) | (j,i) \in \mbox{Next-Edge}_{j} \}$\\
\> \> \> \> $\cup$ $\{(i,\mbox{\rm end}) | (j, \mbox{\rm end}) \in \mbox{Next-Edge}_{j}\}$; \\
\lct \> \> \> Local-Prev-Support$(i,a)$ := \=$\{(i,x) | (i,x) \in E \wedge (x,i) \in \mbox{Prev-Edge}_{i} \}$\\
\> \> \> \> $\cup$ $\{(i,\mbox{\rm start}) | (\mbox{\rm start},i) \in \mbox{Prev-Edge}_{i}\}$; \\ 
\lct  \> \> \> Local-Next-Support$(i,a)$ := \=$\{(i,x) | (i,x) \in E \wedge (i,x) \in \mbox{Next-Edge}_{i} \}$\\
\> \> \> \> $\cup$ $\{(i,\mbox{\rm end}) | (i, \mbox{\rm end}) \in \mbox{Next-Edge}_{i}\}$; {\bf $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}
}

\centerline{\psfig{figure=arc_support.ps,height=1.2in}} 
\vskip .05in
%\renewcommand{\arraystretch}{1.2}
\centerline{\scriptsize
\begin{tabular}[b]{|l l|}
\hline
\rule[0.05in]{0in}{0.1in}Prev-Support$[(1,2), a]=\{(1,2)\}$ & 
Next-Support$[(1,2), a]=\{(1,3)\}$ \\
Prev-Support$[(1,3), a]=\{(1,2),(1,3)\}$ & 
Next-Support$[(1,3), a]=\{(1,\mbox{\rm end})\}$ \\
Prev-Support$[(1,2), b]=\{(1,2)\}$ & 
Next-Support$[(1,2), b]=\{(1,3)\}$ \\
Prev-Support$[(1,3), b]=\{(1,2),(1,3)\}$ & 
Next-Support$[(1,3), b]=\{(1,\mbox{\rm end})\}$ \\
Prev-Support$[(2,1), c]=\{(2, \mbox{\rm start})\}$ & 
Next-Support$[(2,1), c]=\{(2,1), (2,3)\}$ \\
Prev-Support$[(2,3), c]=\{(2,3), (2, 1)\}$ &
Next-Support$[(2,3), c]=\{(2, \mbox{\rm end})\}$ \\
Prev-Support$[(3,1), d]=\{(3, \mbox{\rm start})\}$ &
Next-Support$[(3,1), d]=\{(3,1), (3,2)\}$ \\
Prev-Support$[(3,2), d]=\{(3, 1)\}$ &
\rule[-0.07in]{0in}{0.1in}Next-Support$[(3,2), d]=\{(3, 2)\}$ \\
\hline
\rule[0.05in]{0in}{0.1in}Local-Prev-Support$(1,a)=\{(1,\mbox{\rm start})\}$ &
Local-Next-Support$(1,a)=\{(1,2),(1,3)\}$ \\ 
Local-Prev-Support$(1,b)=\{(1,\mbox{\rm start})\}$ &
Local-Next-Support$(1,b)=\{(1,2),(1,3)\}$ \\ 
Local-Prev-Support$(2,c)=\{(2,1)\}$ & 
Local-Next-Support$(2,c)=\{(2,3)\}$ \\
Local-Prev-Support$(3,d)=\{(3,1),(3,2)\}$ &
\rule[-0.07in]{0in}{0.1in}Local-Next-Support$(3,d)=\{(3,\mbox{\rm end})\}$ \\
\hline
\end{tabular}}
\caption{Initialization of the data structures for MUSE AC-1
along with a simple example.}
\label{preprocess}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
\initlct
\lct \hspace{.05in} {\bf while} \= $List \not = \phi$ {\bf do} {\bf $\{$ }\\
\lct  \> Pop $[(i,j), a]$ from $List$; \\
\lct  \> {\bf for} \= $(j, b) \in$ S$[(i,j), a]$ {\bf do} {\bf $\{$ }\\
\lctl{dec-count}  \> \> Counter$[(j,i), b]$ := Counter$[(j,i), b]-1$; \\
\lct  \> \>	{\bf if} \=  Counter$[(j,i), b]=0$ $\wedge$ M$[(j,i), b]=0$ {\bf then} {\bf $\{$ }\\
\lctl{counter-list} \> \> \> $List := List \cup \{[(j,i), b]\}$; \\
\lct \> \> \> M$[(j,i), b] := 1$;  {\bf $\}$ $\}$ }\\
\lct \> {\sc Update-Support-Sets}($[(i,j), a]$);   (see Figure
\ref{update_dag}) {\bf $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}
}
\caption{Eliminating inconsistent labels from the domains in MUSE AC-1.}
\label{muse_csp_arc_algorithm}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
{\sc Upda}\={\sc te-Support-Sets} ($[(i,j), a]$) {\bf $\{$ }\\
\initlct
\lct \> {\bf for} \=$(i,x) \in$ Prev-Support$[(i,j), a]$ $\wedge$ $x
\neq j$ $\wedge$ $x \neq {\rm start}$ {\bf do} {\bf $\{$ }\\
\lct \> \> Prev-Support$[(i,j), a]$ := Prev-Support$[(i,j), a] - \{(i,x)\}$ ;\\
\lctl{dec-next} \> \> Next-Support$[(i,x), a]$ := Next-Support$[(i,x), a] - \{(i,j)\}$; \\
\lctl{next-nul} \> \> {\bf if} \=Next-Support$[(i,x), a]=\phi$ $\wedge$ M$[(i,x), a]=0$ {\bf then} {\bf $\{$ }\\
\lctl{next-list} \> \> \> $List := List \cup \{[(i,x), a]\}$; \\
\lct  \> \> \> M$[(i,x), a] := 1$; {\bf $\}$ $\}$ }\\
\lct \> {\bf for} \= $(i,x) \in$ Next-Support$[(i,j), a]$ $\wedge$ $x
\neq j$ $\wedge$ $x \neq {\rm end}$ {\bf do} {\bf $\{$ }\\
\lct \> \> Next-Support$[(i,j), a]$ := Next-Support$[(i,j), a] - \{(i,x)\}$;\\
\lctl{dec-prev} \> \> Prev-Support$[(i,x), a]$ := Prev-Support$[(i,x), a] - \{(i,j)\}$; \\
\lctl{prev-nul} \> \> {\bf if} \= Prev-Support$[(i,x), a]=\phi$ $\wedge$
M$[(i,x), a]=0$ {\bf then} {\bf $\{$ }\\
\lctl{prev-list}  \> \> \> $List := List \cup \{[(i,x), a]\}$; \\
\lct  \> \> \> M$[(i,x), a] := 1$; {\bf $\}$ $\}$ }\\
\lct \> {\bf if} \= $(j,i) \in$ Prev-Edge$_{i}$ {\bf then}\\
\lctl{dec-local-prev} \> \> Local-Prev-Support$(i,a)$ := Local-Prev-Support$(i,a) - \{(i,j) \}$; \\
\lctl{local-prev-nul} \> {\bf if} \= Local-Prev-Support$(i,a)=\phi$ {\bf then} {\bf $\{$ }\\
\lctl{domain-del1} \> \> $L_{i} := L_{i} - \{a\}$; \\
\lct \> \> {\bf for} \= $(i,x) \in$ Local-Next-Support$(i,a)$ $\wedge$ $x
\neq j$ $\wedge$ $x \neq {\rm end}$ {\bf do} {\bf $\{$ }\\
\lct  \> \> \> Local-Next-Support$(i,a)$ :=  Local-Next-Support$(i,a) - \{(i,x)\}$;\\
\lct \> \> \> {\bf if} \=  M$[(i,x), a]=0$ {\bf then} {\bf $\{$ }\\
\lctl{local-prev-list}  \> \> \> \> $List := List \cup \{[(i,x), a]\}$; \\
\lct \> \> \> \>  M$[(i,x), a] := 1$; {\bf $\}$ $\}$ $\}$ }\\
\lct \> {\bf if} \= $(i,j) \in$ Next-Edge$_i$ {\bf then}\\
\lctl{dec-local-next} \> \> Local-Next-Support$(i,a)$ := Local-Next-Support$(i,a) - \{(i,j) \}$; \\
\lctl{local-next-nul} \> {\bf if} \= Local-Next-Support$(i,a)=\phi$ {\bf then} {\bf $\{$ }\\
\lctl{domain-del2} \> \> $L_{i} := L_{i} - \{a\}$; \\
\lct \> \> {\bf for} \= $(i,x) \in$ Local-Prev-Support$(i,a)$ $\wedge$ $x
\neq j$ $\wedge$ $x \neq {\rm start}$ {\bf do}  {\bf $\{$ }\\
\lct \> \> \> Local-Prev-Support$(i,a)$ :=  Local-Prev-Support$(i,a) -  \{(i,x)\}$;\\
\lct \> \> \> {\bf if} \=  M$[(i,x), a]=0$ {\bf then} {\bf $\{$ }\\
\lctl{local-next-list} \> \> \> \> $List := List \cup \{[(i,x), a]\}$; \\
\lct \> \> \> \>  M$[(i,x), a] := 1$;  {\bf $\}$ $\}$ $\}$ $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}
}
\caption{The function {\sc Update-Support-Sets}($[(i,j),a]$) for  MUSE AC-1.}
\label{update_dag}
\end{figure}

     To illustrate how these data structures are used by the second
step of MUSE AC-1 shown in Figure \ref{muse_csp_arc_algorithm},
consider what happens if initially $[(1,3),a] \in List$ for the MUSE
CSP depicted in Figure \ref{preprocess}.  $[(1,3),a]$ is placed on
$List$ to indicate that the label $a$ in $L_{1}$ is not supported by
any of the labels associated with node $3$.  When that value is popped
off $List$, it is necessary for each $(3, x) \in$ S$[(1,3),a]$ to
decrement Counter$[(3,1), x]$ by one.  If any Counter$[(3,1), x]$
becomes 0, and $[(3,1),x]$ has not already been placed on the $List$,
then it is added for future processing.  Once this is done, it is
necessary to remove $[(1,3),a]$'s influence on the MUSE DAG.  To
handle this, we examine the two sets Prev-Support$[(1,3),a] = \{(1,2),
(1,3)\}$ and Next-Support$[(1,3),a] = \{(1,{\rm end})\}$.  Note that
the value $(1,{\rm end})$ in Next-Support$[(1,3),a]$ and the value
$(1,3)$ in Prev-Support$[(1,3),a]$, require no further action because
they are dummy values.  However, the value $(1,2)$ in
Prev-Support$[(1,3),a]$ indicates that $(1,3)$ is a member of
Next-Support$[(1,2), a]$, and since $a$ is not admissible for $(1,3)$,
$(1,3)$ should be removed from Next-Support$[(1,2), a]$, leaving an
empty set.  Note that because Next-Support$[(1,2),a]$ is empty, and
assuming that M$[(1,2),a] = 0$, $[(1,2),a]$ is added to $List$ for
further processing.  Next, $(1,3)$ is removed from
Local-Next-Support$(1,a)$, leaving a set of $\{(1,2)\}$. During the
next iteration of the while loop $[(1,2),a]$ is popped from $List$.
When Prev-Support$[(1,2),a]$ and Next-Support$[(1,2),a]$ are
processed, Next-Support$[(1,2),a] = \phi$ and Prev-Support$[(1,2),a]$
contains only a dummy, requiring no action.  Finally, when $(1,2)$ is
removed from Local-Next-Support$(1,a)$, the set becomes empty, so $a$
is no longer compatible with any segment containing node $1$ and can
be eliminated from further consideration as a possible label for node
$1$.  Once $a$ is eliminated from node $1$, it is also necessary to
remove the support of $a \in L_{1}$ from all labels on nodes that
precede node $1$, that is for all nodes $x$ such that $(1,x) \in$
Local-Prev-Support$(1,a)$.  Since Local-Prev-Support$(1,a) = \{(1,{\rm
start})\}$, and {\rm start\/} is a dummy node, there is no more work
to be done.

In contrast, consider what happens if initially
$[(1,2),a] \in  List$ for the MUSE CSP in Figure \ref{preprocess}.  
In this case, Prev-Support$[(1,2), a]$ contains $(1,2)$ which requires
no additional work; whereas, Next-Support$[(1,2),a]$ contains $(1,3)$,
indicating that $(1,2)$ must be removed from
Prev-Support$[(1,3),a]$'s set. After the removal,
Prev-Support$[(1,3),a]$ is non-empty, so the segment containing 
nodes $1$ and $3$ still supports the label $a$ in $L_{1}$.
The reason that these two cases provide different results is that the
constraint arc between nodes $1$ and $3$ is contained in every segment; whereas, 
the constraint arc between nodes $1$ and $2$ is found in only one of them.

\subsection{The Running Time and Space Complexity of MUSE AC-1}

The worst-case running time of the routine to initialize the MUSE AC-1
data structures (in Figure \ref{preprocess}) is O$(n^{2}l^{2} +
n^{3}l)$, where $n$ is the number of nodes in a MUSE CSP and $l$ is
the number of labels.  Given that the number of $(i,j)$ elements in
$E$ is O$(n^{2})$ and the domain size is O$(l)$, the size of the
Counter and S arrays is O$(n^{2}l)$.  To determine the number of
supporters for a given arc-label pair requires O$(l)$ work; hence,
initializing the Counter and S arrays requires O$(n^{2}l^{2})$ time.
However, there are O$(n^{2}l)$ Prev-Support and Next-Support sets,
where each Prev-Support$[(i,j),a]$ and Next-Support$[(i,j),a]$
requires O$(n)$ time to compute, so the time to calculate all
Prev-Support and Next-Support sets is O$(n^{3}l)$.  Finally, the time
needed to calculate all Local-Next-Support and Local-Prev-Support sets
is O$(n^{2}l)$ because there are O$(nl)$ sets with up to O$(n)$
elements per set.

The worst-case running time for the algorithm which prunes labels that are not MUSE
arc consistent (in Figures \ref{muse_csp_arc_algorithm} and \ref{update_dag}) also operates
in O$(n^{2}l^{2} + n^{3}l)$ time.
Clearly the Counter array contains O$(n^{2}l)$ entries (a similar argument
can be made for the S array) 
to keep track of in the
algorithm.  Each Counter$[(i,j),a]$ can be at most $l$ in magnitude, and it can
never become negative, so the maximum running time for line \ref{dec-count} in
Figure \ref{muse_csp_arc_algorithm}
(given that elements appear on $List$ only once because of M)
is O$(n^{2}l^{2})$.  Because there are O$(n^{2}l)$ Next-Support
and Prev-Support lists, each up to O$(n)$ in size, the maximum running time
required for lines \ref{dec-next} and \ref{dec-prev} in Figure \ref{update_dag} is O$(n^{3}l)$.  Finally, since there are
O$(nl)$ Local-Prev-Support and Local-Next-Support sets from which to eliminate
O$(n)$ elements, the  maximum running time of lines \ref{dec-local-prev}
and \ref{dec-local-next} in Figure \ref{update_dag} is
O$(n^{2}l)$.  Hence, the  maximum running time of the MUSE CSP arc consistency
algorithm is O$(n^{2}l^{2} + n^{3}l)$.

The space complexity of MUSE CSP AC-1 is also O$(n^{2}l^{2} + n^{3}l)$
because the arrays Counter and M contain O$(n^{2}l)$ elements, and
there are  O$(n^{2}l)$ S sets, each containing O$(l)$ items;
O$(n^{2}l)$ Prev-Support and Next-Support sets, each containing O$(n)$ items; and
O$(nl)$ Local-Next-Support and Local-Prev-Support sets, each containing 
O$(n)$ items.  


By comparison, the  worst-case running time and space complexity for CSP arc consistency is
O$(n^{2}l^{2})$, assuming that there are $n^{2}$ constraint arcs.  
Note that for applications where $l=n$,
the  worst-case running times of the algorithms are the same order (this is true for
parsing spoken language with a MUSE CSP).  Also, if $\Sigma$ is
representable as planar DAG (in terms of Prev-Edge and Next-Edge, not E), then
the running times of the two algorithms are the same order because the average
number of values in Prev-Support and Next-Support would be a constant.
On the other hand, if we compare MUSE CSP to the use of multiple CSPs for problems where
there are $k$ alternative variables for a particular variable in a
CSP,  then MUSE CSP AC-1 is asymptotically more attractive, 
as shown in Table \ref{table1}.  

\begin{table*}[t]
\renewcommand{\baselinestretch}{.80}
\begin{center}
\begin{tabular}{@{\hspace{0in}}|c@{\hspace{0.05in}}||c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|}
\hline

\vspace*{-.05in}Approach \ & Nodes & Degree of  & Number of & Number of &
Asymptotic\\
\ & per Path  & Node splitting & Constraint Networks & Nodes & Time\\
\hline
\hline
 CSPs &       $n$       &       $k$       &       $k^{n}$      &  $n$  &
$k^{n}n^{2}l^{2}$     \\
\hline
 MUSE CSP &   $n$       &       $k$       &       1       &     $kn$      &
$(kn)^{2}l^{2} + (kn)^{3}l$  \\
\hline
\end{tabular}
\end{center}
\caption{Comparison of the space and time complexity for MUSE arc consistency
on a MUSE CSP to arc consistency on multiple CSPs representing a
node splitting problem (e.g., lexical ambiguity in parsing).}
\label{table1}
\end{table*}

\subsection{The Correctness of MUSE AC-1}

Next we prove the correctness of MUSE AC-1.  



\begin{theorem}
A label $a$ is eliminated from  $L_{i}$ by MUSE AC-1 if and only if that
label is unsupported by all the arcs $(i, x)$ of every segment.
\end{theorem}

\noindent {\bf Proof:}

\begin{enumerate}

\item We must show that if a label is eliminated, it is inadmissible in every
segment.  A label is
eliminated from a domain by MUSE AC-1 (see lines \ref{domain-del1} and
\ref{domain-del2} in Figure \ref{update_dag}) if and only if its
Local-Prev-Support set or its Local-Next-Support set becomes empty
(see lines \ref{local-prev-nul} and \ref{local-next-nul} in Figure
\ref{update_dag}).  In either case, the label should be eliminated to
make the MUSE CSP instance MUSE arc consistent.  We prove that if a label's local support
sets become empty, that label cannot participate in any
MUSE arc consistent instance of MUSE CSP.    This is proven for
Local-Next-Support (Local-Prev-Support follows by symmetry.) Observe
that if $a \in L_{i}$, and it is unsupported by all of the nodes
which immediately follow $i$ in the DAG, then it cannot
participate in any MUSE arc consistent instance of MUSE CSP.  In line
\ref{dec-local-next} of Figure \ref{update_dag}, if $(i,j)$ is removed
from Local-Next-Support$(i,a)$ set then  $[(i,j),a]$ must have been popped
off $List$. The removal of $(i,j)$ from Local-Next-Support$(i,a)$
indicates that, in the segment containing $i$ and $j$, $a \in L_{i}$ is inadmissible. 
It remains to be shown that $[(i,j),a]$ is put on $List$
if $a \in L_{i}$ is unsupported by every segment which
contains $i$ and $j$.  This is proven by induction on the number of
iterations of the while loop in Figure \ref{muse_csp_arc_algorithm}.

{\bf Base case:} The initialization routine only puts $[(i,j),a]$
on $List$ if $a \in L_{i}$ is incompatible with every label in
$L_{j}$ (line \ref{init-list} of Figure \ref{preprocess}).  Therefore, $a \in
L_{i}$ is unsupported by all segments containing $i$ and $j$.

{\bf Induction step:} Assume that at the start of the $k$th
iteration of the while loop all $[(x,y),c]$ which have ever been put
on $List$ indicate that $c \in L_{x}$ is  inadmissible in  every
segment which contains $x$ and $y$.  It remains to show that during
the $k$th iteration, if $[(i,j), a]$ is put on $List$, then $a \in
L_{i}$ is unsupported by every segment which contains $i$ and $j$.
There are several ways in which a new $[(i,j), a]$ can be put on $List$:
\begin{enumerate}
\item All labels in $L_{j}$ which were once compatible with $a \in
L_{i}$ have been eliminated. This item could have been placed on
$List$ either during initialization (see line \ref{init-list} in
Figure \ref{preprocess}) or during a previous iteration of the while
loop (see line \ref{counter-list} in Figure
\ref{muse_csp_arc_algorithm})), just as in the CSP AC-4 algorithm.  
It is obvious that, in this case, $a \in L_{i}$ is
inadmissible in  every segment containing $i$ and $j$.

\item 
Prev-Support$[(i,j),a]=\phi$ (see line \ref{prev-nul} in Figure
\ref{update_dag}) indicating that $a\in L_{i}$ is incompatible with
all nodes $k$ for $(k,j) \in$ Prev-Edge$_{j}$.  The only way for
$[(i,j),a]$ to be placed on $List$ for this reason (at line
\ref{prev-list}) is because all tuples of the form $[(i,k),a]$ (where
$(k,j) \in$ Prev-Edge$_{j}$) were already put on $List$.  By the
induction hypothesis, these $[(i,k), a]$ items were placed on the
$List$ because $a \in L_{i}$ is inadmissible in with all segments
containing $i$ and $k$ in the DAG.  But if $a$ is not supported by
any node which immediately precedes $j$ in the DAG, then $a$ is
unsupported by every segment which contains $j$.  Therefore, it is
correct to put $[(i,j), a]$ on $List$.

\item 
Next-Support$[(i,j),a]=\phi$ (see line \ref{next-nul} in Figure
\ref{update_dag}) indicating that $a\in L_{i}$ is incompatible with
all nodes $k$ for $(j,k) \in$ Next-Edge$_{j}$.  The only way for
$[(i,j),a]$ to be placed on $List$ (at line \ref{next-list}) for this
reason is because all tuples of the form $[(i,k),a]$ (where $(j,k)
\in$ Next-Edge$_{j}$) were already put on $List$.  By the induction
hypothesis, these $[(i,k), a]$ items were placed on the $List$ because
$a \in L_{i}$ is inadmissible in all segments containing $i$ and $k$
in the DAG.  But if $a$ is not supported by any node which
immediately follows $j$ in the DAG, then $a$ is inadmissible in
every segment which contains $j$.  Therefore, it is correct to put
$[(i,j), a]$ on $List$.

\item 
Local-Next-Support$(i,a)=\phi$ (see line \ref{local-next-nul} in
Figure \ref{update_dag}) indicating that $a\in L_{i}$ is incompatible with
all nodes $k$ such that $(i,k) \in$ Next-Edge$_{i}$.  The only
way for $[(i,j),a]$ to be placed on $List$ (at line
\ref{local-next-list}) for this reason is because no node which
follows $i$ in the DAG supports $a$, and so all pairs $(i,k)$ have
been legally removed from Local-Next-Support$(i,a)$ during previous
iterations.  Because there is no segment containing $i$ which supports
$a$, it follows that no segment containing $i$ and $j$ supports that
label.


\item 
Local-Prev-Support$(i,a)=\phi$ (see line \ref{local-prev-nul} in
Figure \ref{update_dag}) indicating that $a\in L_{i}$ is incompatible with
all nodes $k$ such that $(k,i) \in$ Prev-Edge$_{i}$.  The only
way for $[(i,j),a]$ to be placed on $List$ (at line
\ref{local-prev-list}) for this reason is because no node which
precedes $i$ in the DAG supports $a$, and so all pairs $(i,k)$ have
been legally removed from Local-Prev-Support$(i,a)$ during previous
iterations.  Because there is no segment containing $i$ which supports
$a$, it follows that no segment containing $i$ and $j$ supports that
label.
\end{enumerate}

\noindent At the beginning of the ($k+1$)th iteration of the while loop,
every $[(x,y), c]$ on $List$ implies that $c$ is not supported by any
segment which contains $x$ and $y$.  Therefore, by induction, it
is true for all iterations of the while loop in Figure
\ref{muse_csp_arc_algorithm}.  Hence, if a label's local support sets
become empty, that label cannot participate in a
MUSE arc consistent instance of MUSE CSP.


\item We must also show that if $a$ is not eliminated from  $L_{i}$ by
the MUSE arc consistency algorithm, then
it must be MUSE arc consistent.  For $a$ to be MUSE arc consistent,
there must exist at least one path from {\rm start} to {\rm end} which
goes through node $i$ such that all nodes $n$ on that path contain at
least one label which is compatible with $a \in L_{i}$.
If $a$ is not deleted after MUSE AC-1, then
Local-Next-Support$(i,a)\not=\phi$ and Local-Prev-Support$(i,a)\not=\phi$.  
Hence, $i$ must be preceded and followed by at least one node which
supports $a \in L_{i}$; otherwise, $a$ would have been deleted. 
As depicted in Figure \ref{three-nodes}, we know that there must be
some node $j$ which precedes $i$ such that, if it is not {\rm start},
it must
contain at least one label $b$ which supports $a$, and
Next-Support$[(i,j),a]$ and  Prev-Support$[(i,j),a]$ must be non-empty.
Similarly, there must be some node $k$ which follows $i$ such that, if
it is not {\rm end}, it must
contain at least one label $c$ which supports $a$, and
Next-Support$[(i,k),a]$ and  Prev-Support$[(i,k),a]$ must be
non-empty.


\begin{figure}
\centerline{\psfig{figure=three.ps,height=2in}}
\caption{If $a \in L_{i}$ after MUSE AC-1, it must be preceded by
some node $j$ and followed by some node $k$ which support $a$.}
\label{three-nodes}
\end{figure}

To show there is a path through the DAG, we must show that there is a
path beginning at {\rm start} which reaches $i$ such that all the
nodes along that path support $a \in L_{i}$, and that there is a
path beginning at $i$ which reaches {\rm end} such that all the
nodes along that path support $a \in L_{i}$.  We will show the
necessity of the path from $i$ to {\rm end} such that all nodes along
that path support $a \in L_{i}$ given that $a$ remains after MUSE
AC-1; the necessity of the path
from {\rm start} to $i$ can be shown in a similar way.

{\bf Base case:} If $a \in L_{i}$ after MUSE AC-1, then there must
exist at least one node which follows $i$, say $k$, such that
$[(i,k),a]$ has never been placed on $List$.  Hence,
$R{\it 2}(i,a,k,c)=1$ for at least one $c \in L_{k}$ and
Next-Support$[(i,k),a]$ and  Prev-Support$[(i,k),a]$ must be
non-empty.

{\bf Induction Step:} Assume that there is a path of $n$ nodes that
follows $i$ that supports $a \in L_{i}$, but none of those
nodes is the {\rm end} node.  This implies that each of
the $n$ nodes contains at least one label compatible with $a$ and that
Next-Support$[(i,n),a]$ and  Prev-Support$[(i,n),a]$ must be non-empty
for each of the $n$ nodes.

Next, we show that a path of length $(n+1)$
must also support $a \in L_{i}$; otherwise, the label
$a$ would have been deleted by MUSE AC-1.  We have already noted that 
for the $n$th node on the path in the induction step,
Next-Support$[(i,n),a]$ must be non-empty; hence, there must exist at
least one node, say $n'$, which follows the $n$th node in the path of
length $n$ which supports $a \in L_{i}$.  If $n'$ is the {\rm end} node, then
this is the case.  If $n'$ is not {\rm end}, then the only way that
$(i,n')$ can be a member of Next-Support$[(i,n),a]$ is if $[(i,n'),a]$
has not been placed on $List$.  If it hasn't, then $R{\it
2}(i,a,n',l)=1$ for at least one $l\in L_{n'}$ and
Next-Support$[(i,n'),a]$ and  Prev-Support$[(i,n'),a]$ must be
non-empty.  If this were not the case, then $(i,n')$ would have been
removed from Next-Support$[(i,n),a]$, and $n$ would no longer support
$a \in L_{i}$.

Hence, if $a \in L_{i}$ after MUSE AC-1, then there must be a path of
nodes to {\rm end} such that for each node $n$ which is not the {\rm
end} node,
$R{\it 2}(i,a,n,l)=1$ for at least one $l\in L_{n}$ and
Next-Support$[(i,n),a]$ and  Prev-Support$[(i,n),a]$ must be
non-empty.   Hence $a$ is MUSE arc consistent.\\
$\Box$
\end{enumerate}



From this theorem, we may conclude
that MUSE AC-1 builds the largest MUSE arc consistent structure.
Because MUSE arc consistency takes into account all of its segments,
if a single CSP were selected from the MUSE CSP after MUSE arc
consistency is enforced, CSP arc consistency could eliminate
additional labels.

\subsection{A Profile of MUSE AC-1}

Given the fact that MUSE AC-1 operates on a composite data structure,
the benefits of using this algorithm can have a high payoff over
individually processing CSPs.  In section 2.4, we provided several
examples where the payoff is obvious.  To gain some insight into
factors influencing the effectiveness of MUSE CSP, we have conducted
an experiment in which we randomly generate MUSE CSP instances with
two different graph topologies.  The {\em tree} topology is
characterized by two parameters: the {\em branching factor} (how many
nodes follow each non-leaf node in the tree) and the {\em path length}
(how many nodes there are in a path from the root node to a leaf
node).  The {\em lattice} topology is characteristic of a MUSE CSP
which is produced by a hidden-Markov-model-based spoken language
recognition system for our constraint-based parser.  Lattices are also
characterized by their length and their branching factor.

For this experiment, we examined trees
with a path length of four and a branching factor of two or three, and 
lattices with a path length of four and a branching factor of two or three.
We initialized each variable to have either 3 or 6 labels.  
We then randomly generated constraints in
the network, varying the probability that $R{\it 2}(i,a,j,b)$ = 1
from 0.05 to .95 in steps of 0.05. For each probability, 6 instances
were generated.   The lower the probability
that $R{\it 2}(i,a,j,b)$ = 1, the tighter the constraints.  Note
that the probability of a constraint between
two nodes should be understood as the probability of a constraint
between two nodes given that a constraint is allowed between them.
For example, nodes that are on the same level in the tree topology are
in different segments, and so constraints cannot occur between them.

The results of this experiment are displayed in Figures \ref{trees}
and \ref{lattices}. In each of the four panels of each figure, four curves are displayed.
{\em After MUSE AC-1\/} appears on curves displaying the average number of
labels remaining after MUSE AC-1 is applied to instances of a MUSE CSP
as the probability of a constraint varies.  The curves labeled {\em
Solution\/} indicate the average number of labels
remaining after MUSE AC-1 that are used in a solution.  
{\em CSP AC\/} is associated with curves that display the number
of labels that remain in at least one segment when the
segment is extracted from the MUSE CSP and CSP arc consistency is
applied.  {\em Unused} indicates the difference between the number 
of labels that remain after MUSE AC-1 and the number that are CSP
arc consistent in at least one segment.


\begin{figure}
\begin{tabular}{|c|c|}
\hline
\ \\
\psfig{figure=tree1.ps,width=3in}
\psfig{figure=tree3.ps,width=3in}
\\ \hline
\ \\
\psfig{figure=tree2.ps,width=3in}
\psfig{figure=tree4.ps,width=3in}
\\ \hline
\end{tabular}
\caption{Simulation results for trees with a path length of 4, a branching factor of 2 or
3, and 3 or 6 labels per variable.}
\label{trees}
\end{figure}
\begin{figure}
\begin{tabular}{|c|c|}
\hline
\ \\
\psfig{figure=latt1.ps,width=3in}
\psfig{figure=latt3.ps,width=3in}
\\ \hline
\ \\
\psfig{figure=latt2.ps,width=3in}
\psfig{figure=latt4.ps,width=3in}
\\ \hline
\end{tabular}
\caption{Simulation results for lattices with a path length of 4, a branching factor of 2 or
3, and 3 or 6 labels per variable.}
\label{lattices}
\end{figure}



For both of the topologies, if the
probability  $R{\it 2}(i,a,j,b)$ = 1 is low (e.g., .1) or
high (e.g., .8), then MUSE AC-1 tracks the performance of arc
consistency performed on the individual instances for either topology.
However, the topology does impact the range of low and high
probabilities for which this is true.
When constraints are randomly generated,  after
MUSE AC-1 is performed, the tree topology has fewer remaining values
than the lattice topology that are not CSP arc consistent.   
These results suggest that MUSE
CSP AC-1 may be more effective for some topologies than for others.
However, in the tree topology the randomly generated constraints
between the values of two variables are independent of the other
probabilities generated.  This is not the case for the lattice; once
a pair of variables has a set of randomly generated constraints, they
are shared by all paths through the lattice. Notice that increasing
the number of values in a domain seems to have more impact on the
tree than increasing the branching factor, probably because as the
branching factor increases, so does the number of independent nodes.

This experiment does show  that if a problem is tightly constrained, MUSE
AC-1 can be effectively used to eliminate values that are unsupported
by the constraints.  Clearly, this was the case for the parsing
problems presented in section 2.4.  A small set of syntactic
constraints  effectively eliminates values that can never be 
used in a parse for a sentence, even in a lattice with a branching
factor of three and arbitrarily long paths. 


\subsection{Extracting Solutions from a MUSE CSP after MUSE AC-1}

Solutions to regular CSP problems are typically generated by
using backtracking (or fancier search algorithms) to assemble a set of
labels, one for each node, which are consistently admissible.
Extracting solutions from MUSE CSPs can be done in a similar way, but
it is desirable to make a few modifications to the search algorithms
to take advantage of the extra information which is contained in the
MUSE AC-1 data structures.

Consider the example shown in Figure \ref{extract_solutions}.
This figure presents a simple MUSE CSP.  Suppose we are only interested in solutions to
the segment which is highlighted: $\{$A, B, C, D$\}$.  
Suppose also that there is only one solution to this
segment: a1 for A, b3 for B, c1 for C,
and d1 for D.  We wish to find this solution by
depth-first search.

We begin by assigning a1 to A.  However, the domain of
B, in addition to the desired label b3, also contains the
labels b1 and b2, which are valid only for other segments.  If
we initially (and naively) choose b1 for B and continue
doing depth-first search, we would waste a lot of time backtracking.
Fortunately, after enforcing MUSE arc consistency, the MUSE data
structures contain useful information concerning the segments for which the
labels are valid.  In this case, the backtracking algorithm can
check Local-Next-Support(B, b1) to determine which of the
outgoing nodes b1 is compatible with.  Since (B, C) is
not an element of Local-Next-Support(B, b1), a smart search
algorithm would not choose b1 as a label for B.

However, just looking at the local support sets might not be
enough.  After the search algorithm has rejected b1 as a label for
B, it would go on to consider b2.
Local-Next-Support(B, b2) indicates that b2 is a valid
label for some of the segments which contain C, but it fails to
tell us that b2 is not valid for the segment we are examining.
Despite this, the search algorithm can still eliminate b2 by
looking at Next-Support[(B, C), b2], which indicates
that b2 is only compatible with segments containing the node F.
Clearly, this type of information will more effectively guide the search for a
solution along a certain path.  Improved search strategies for MUSE
CSPs will be the focus of future research efforts.

\begin{figure}
\centerline{\psfig{figure=extract2.ps,width=5.5in}}
\caption{Using MUSE arc consistency data structures to guide a
backtracking search.}
\label{extract_solutions}
\end{figure}

\section{The MUSE CSP Path Consistency Algorithm}

In this section, we introduce an algorithm to achieve MUSE CSP 
path consistency, MUSE PC-1, which builds upon the
PC-4 algorithm \cite{hanandlee}.

\subsection{MUSE PC-1}

MUSE path consistency is enforced by setting $R{\it
2}(i,a,j,b)$ to false when it violates the conditions of Definition
\ref{muse_path_consistency_def}.  MUSE PC-1 builds and maintains
several data structures comparable to the data structures defined for
MUSE AC-1, described in Figure \ref{notation2}, to allow it to efficiently perform this operation.
Figure \ref{preprocess_path} shows the code for initializing the data
structures, and
Figures \ref{muse_csp_path_algorithm} and \ref{update_dag2} contain the 
algorithm for eliminating MUSE path inconsistent binary constraints.

\begin{figure}
\tabcolsep .05in
\renewcommand{\baselinestretch}{.85}

\centerline{\footnotesize
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c} {\bf \ \ \ Notation\ \ \ } & 
\multicolumn{1}{|c|} {\bf Meaning
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}
} \\
\hline
\hline
$(i,j)$ &
\begin{tabular}{l}
An ordered pair of nodes.
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$E$ &
\begin{tabular}{l}
All node pairs $(i,j)$ such that there exists a path of directed edges in $G$ \\
between $i$ and $j$. If $(i,j) \in E$, then $(j,i) \in E$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$[(i,j), k, a, b]$ & 
\begin{tabular}{l}
An ordered quadruple of a node pair $(i,j)$, a node $k$, and the
labels\\ 
$a \in L_{i}$ and $b \in L_{j}$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$L_{i}$ &
\begin{tabular}{l}
$\{a | a \in L$ and $(i,a)$ is permitted by the constraints (i.e., admissible)$\}$
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$R{\it 2}(i,a,j,b)$ &
\begin{tabular}{l}
$R{\it 2}(i,a,j,b) = 1$ indicates the admissibility $a \in L_i$ and $b \in L_j$ given\\
binary constraints. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Counter$[(i,j), k, a, b]$ & 
\begin{tabular}{l}
The number of labels in $L_{k}$ which are compatible with $R{\it 2}(i,a,j,b)$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
S$[(i,j), k, a, b]$ & 
\begin{tabular}{l}
$(k,c) \in S[(i,j), k, a, b]$ means that $c \in L_{k}$ is compatible
with\\ 
$R{\it 2}(i,a,j,b)$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
M$[(i,j), k, a, b]$ & 
\begin{tabular}{l}
M$[(i,j), k, a, b]=1$ indicates that $R{\it 2}(i,a,j,b)$ is false for
paths\\
including $i$, $j$, and $k$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$List$ &
\begin{tabular}{l}
A queue of path support to be deleted. 
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}\\
\hline
$G$ &
\begin{tabular}{l}
$G$ is the set of node pairs $(i,j)$ such that there exists a directed\\
edge from $i$ to $j$. \\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Next-Edge$_{i}$ & 
\begin{tabular}{l}
Next-Edge$_{i}$ contains all node pairs $(i,j)$ such that there exists
a\\ 
directed edge $(i,j) \in G$.  It also contains $(i, {\rm end})$ if
$i$ is the last\\
node in a segment.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
Prev-Edge$_{i}$ &
\begin{tabular}{l}
Prev-Edge$_{i}$ contains all node pairs $(j,i)$ such that there exists
a \\ 
directed edge $(j,i) \in G$.  It also contains $({\rm start},i)$ if
$i$ is the first\\
node in a segment.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Local-Prev-Support$[(i,j), a, b]$ \ \ &  
\begin{tabular}{l}
A set of elements $(i,k)$ such that $(k,i)\in$ Prev-Edge$_{i}$, and if
$k \neq {\rm start}$,\\
$R{\it 2}(i,a,j,b)$ must be compatible with one of $k$'s labels. If\\
Local-Prev-Support$[(i,j), a, b]$ becomes empty, $R{\it 2}(i,a,j,b)$
becomes false.
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Local-Next-Support$[(i,j), a, b]$ \ \ &
\begin{tabular}{l}
A set of elements $(i,k)$ such that $(i,k) \in$ Next-Edge$_{i}$, and
if $k \neq {\rm end}$,\\
$R{\it 2}(i,a,j,b)$ must be compatible with one of $k$'s labels. If\\
Local-Next-Support$[(i,j), a, b]$ becomes empty, $R{\it 2}(i,a,j,b)$
becomes false.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Prev-Support$[(i,j), k, a, b]$ \ \ &
\begin{tabular}{l}
$(i,x) \in$ Prev-Support$[(i,j),k,a,b]$ implies that $(x,k) \in$ Prev-Edge$_{k}$, and\\
if $x \neq {\rm start}$, then $R{\it 2}(i,a,j,b)$ is  compatible with at least one
of $k$'s and\\ 
one of $x$'s labels. If Prev-Support$[(i,j),k,a,b]$ becomes empty, then\\
$R{\it 2}(i,a,j,b)$ 
is no longer true in segments containing $i$, $j$, and $k$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\ Next-Support$[(i,j), k, a, b]$ \ \ &
\begin{tabular}{l}
$(i,x) \in$ Next-Support$[(i,j), k, a, b]$ means that $(k,x) \in$
Next-Edge$_{k}$, and\\
if $x \neq {\rm end}$, then $R{\it 2}(i,a,j,b)$ is  compatible with at least one
of $k$'s and\\ 
one of $x$'s labels. If Next-Support$[(i,j),k,a,b]$ becomes empty, then\\
$R{\it 2}(i,a,j,b)$  
is no longer true in segments containing $i$, $j$, and $k$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
\end{tabular}
}

\caption{Data structures and notation for MUSE PC-1.}
\label{notation2}
\end{figure}
%\renewcommand{\baselinestretch}{1.5}


MUSE PC-1 must keep track of which labels in $L_{k}$
support $R{\it 2}(i,a,j,b)$.  To keep
track of how much path support each $R{\it 2}(i,a,j,b)$
has, the number of labels in $L_{k}$ which satisfy 
$R{\it 2}(i,a,k,c)$ and $ R{\it 2}(k,c,j,b)$ are counted using
Counter$[(i,j),k,a,b]$.  Additionally, the algorithm
must keep track of the set S$[(i,j),k,a,b]$, which contains members
of the form $(k,c)$ where $R{\it 2}(i,a,k,c)$ and $R{\it 2}(k,c,j,b)$
are supported by $R{\it 2}(i,a,j,b)$.  If $R{\it
2}(i,a,j,b)$ ever becomes false in the segment containing $i$, $j$,
and $k$, then $R{\it 2}(i,a,k,c)$ and $R{\it 2}(k,c,j,b)$ will loose
some of their support.   MUSE PC-1 also uses the
Local-Next-Support, Local-Prev-Support, Prev-Support, and Next-Support
sets similar to those in MUSE AC-1. 

MUSE PC-1 is able to use the
properties of the DAG to identify local (and hence efficiently
computable) conditions under which binary constraints fail because
of lack of path support. Consider Figure \ref{local_path_dag}, which shows the nodes
which are adjacent to node $i$ and $j$ in the DAG.  Because
every segment in the DAG which contains node $i$ and $j$ is
represented as a directed path in the DAG going through both node $i$ and node $j$, some
node must precede and follow nodes $i$ and $j$ for $R{\it 2}(i,a,j,b)$
to hold.  In order to track this
dependency, two sets are maintained for each $[(i,j), a, b]$ tuple:
Local-Prev-Support$[(i,j), a, b]$ and Local-Next-Support$[(i,j), a,
b]$.  Note that we distinguish Local-Prev-Support$[(i,j), a, b]$ from
Local-Prev-Support$[(j,i), b, a]$ to separately keep track of those elements
directly preceding $i$ and those directly preceding $j$.  
We also distinguish Local-Next-Support$[(i,j), a, b]$ from
Local-Next-Support$[(j,i), b, a]$.  If any of these sets become empty, then
the $(i,j)$ arc can no longer support $R{\it 2}(i,a,j,b)$.
Local-Prev-Support$[(i,j), a, b]$ is a set of ordered node pairs
$(i,x)$ such that $(x,i) \in$ Prev-Edge$_{i}$, and  if $(i,x) \in E$, there is at least
one label $d \in L_{x}$ which is compatible with $R{\it 2}(i,a,j,b)$.
Local-Next-Support$[(i,j), a, b]$ is a set of ordered node pairs
$(i,x)$ such that $(i,x) \in$ Next-Edge$_{i}$, and if $(i,x) \in E$, there is at least
one label $d \in L_{x}$ which is compatible with $R{\it 2}(i,a,j,b)$.
Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when $({\rm start},i) \in$ Prev-Edge$_{i}$, $(i,{\rm start})$ is  added to
Local-Prev-Support$[(i,j),a,b]$, and when $(i,{\rm end}) \in$ Next-Edge$_{i}$,
$(i,{\rm end})$ is added to Local-Next-support$[(i,j),a,b]$.  
\begin{figure}
\centerline{\psfig{figure=local_path_dag.ps,height=3in}}
\caption{Local-Prev-Support and Local-Next-Support for the path
consistency of an example DAG. The solid directed lines are members of $G$, and
the solid undirected line represents the $(i,j)$ and $(j,i)$ members of $E$.}
\label{local_path_dag}
\end{figure}

The algorithm can utilize similar conditions for nodes which may not be
directly connected to $i$ and $j$.
Consider Figure \ref{far_path_dag}. Suppose that $R{\it 2}(i,a,j,b)$
is compatible with a label in
$L_{k}$, but is incompatible with 
the labels in $L_{x}$ and $L_{y}$, then
$R{\it 2}(i,a,j,b)$ and  $R{\it 2}(j,b,i,a)$ are false for all segments containing 
$i$, $j$, and $k$ because those segments would have to
include either node $x$ or $y$.   To determine whether a
constraint is admissible for a set of segments containing $i$, $j$, and $k$,
we calculate Prev-Support$[(i,j), k, a, b]$, Prev-Support$[(j,i), k,
b,a]$, Next-Support$[(i,j), k, a, b]$, and  Next-Support$[(j,i),k,b,a]$
sets. Next-Support$[(i,j),k,a,b]$ includes all $(i,x)$ arcs which
support $R{\it 2}(i,a,j,b)$ given that there is a directed edge from $k$ to
$x$,  $R{\it 2}(i,a,j,b)=1$,  $R{\it 2}(i,a,k,c)=1$, and  $R{\it
2}(k,c,j,b)= 1$ (Next-Support$[(j,i),k,b,a]$ 
is defined similarly). Prev-Support$[(i,j),k,a,b]$
includes all $(i,x)$ arcs which support $R{\it 2}(i,a,j,b)$
given that there is a directed edge from $x$ to $k$, 
$R{\it 2}(i,a,j,b)=1$,  $R{\it 2}(i,a,k,c)=1$, and  $R{\it
2}(k,c,j,b)=1$ (Prev-Support$[(j,i),k,b,a]$ is defined similarly).
Note that Prev-Support$[(i,j),k,a,b]$ will  contain an 
ordered pair $(i,k)$ if $(i,k)$ $\in$ Prev-Edge$_{k}$, and 
$(i,j)$ if $(j,k)$ $\in$ Prev-Edge$_{k}$.  Next-Support$[(i,j),k,a,b]$ 
will contain an ordered pair $(i,k)$ if $(k,i)$ $\in$ Next-Edge$_{k}$
and  $(i,j)$ if $(k,j) \in$ Next-Edge$_{k}$.  These elements
are included because the edge between those nodes
is sufficient to allow the support.  Dummy ordered pairs are also created to
handle cases where a node is at the beginning or end of a network:
when $({\rm start},k) \in$ Prev-Edge$_{k}$, $(i,{\rm start})$ is  added to
Prev-Support$[(i,j),k,a,b]$, and when $(k,{\rm end}) \in$ Next-Edge$_{k}$,
$(i,{\rm end})$ is added to Next-Support$[(i,j),k,a,b]$.  
\begin{figure}
\centerline{\psfig{figure=far_path_dag.ps,height=3.5in}}
\caption{If it is found that $\mbox{Next-Edge}_{k}=\{(k,x),(k,y)\}, \mbox{Counter}[(i,j),x,a,b]= 0, \mbox{ and } \mbox{Counter}[(i,j),y,a,b] = 0$, then  $R{\it 2}(i,a,j,b)$ is ruled out for every segment containing $i$, $j$, and $k$.  The solid directed lines are members of $G$, and the solid undirected lines represent members of $E$.}
\label{far_path_dag}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
\initlct
\lct \hspace{.05in} \=$List := \phi$;\\
\lct \> $E := \{(i,j) | \exists \sigma \in \Sigma : i,j \in \sigma \wedge i
\not = j \wedge i,j \in N \}$;\\
\lct \>  {\bf for }\= $(i,j) \in E$ {\bf do} \\
\lct  \> \> {\bf for} \=  $a \in L_{i}$ {\bf do} \\
\lct  \> \>  \> {\bf for} \=  $b \in L_{j}$ {\bf do} {\bf $\{$ }\\ 
\lct  \> \> \> \> Local-Prev-Support$[(i,j), a, b] := \phi$; Local-Next-Support$[(i,j), a, b] := \phi$;  \\
\lct  \> \> \>  \> {\bf for} \=  $k \in N$ such that $(i,k) \in E \wedge (j,k) \in E$ {\bf do} {\bf $\{$ }\\
\lct \> \> \> \> \> S$[(i,j), k, a, b] := \phi$;  \\
\lct \> \> \> \> \> M$[(i,j), k, a, b] := 0$;  \\
\lct  \> \> \> \> \> Prev-Support$[(i,j), k, a, b] := \phi$;
Next-Support$[(i,j), k, a, b] := \phi$;  {\bf $\}$ } {\bf $\}$ }\\
\lct  \> {\bf for }\= $(i,j) \in E$ {\bf do} \\
\lct  \> \> {\bf for} \=  $a \in L_{i}$ {\bf do} \\
\lct  \> \> \> {\bf for} \= $b \in L_{j}$ such that $R{\it 2}(i,a,j,b)$ {\bf do} {\bf $\{$ }\\
\lct  \> \> \> \> {\bf for} \=  $k \in N$ such that $(i,k) \in E \wedge (j,k) \in E$ {\bf do} {\bf $\{$ }\\
\lct  \> \> \> \> \> Total := 0; \\
\lct  \> \> \> \> \> {\bf for} \= $c \in L_{k}$ {\bf do} \\
\lct  \> \> \> \> \> \> {\bf if} \= $R{\it 2}(i,a,k,c)$ and $R{\it 2}(k,c,j,b)$ {\bf then} {\bf $\{$ }\\
\lct  \> \> \> \> \> \> \> Total := Total+1; \\
\lct  \> \> \> \> \> \> \> S$[(i, k), j, a, c] := $ S$[(i, k), j, a, c] \cup \{(j, b)\}$; {\bf $\}$ }\\
\lct  \> \> \> \> \> {\bf if} \= Total = 0 {\bf then} {\bf $\{$ }\\
\lctl{init-list2}  \> \> \> \> \> \>  $List := List \cup \{[(i,j), k, a, b]\}$; \\
\lct  \> \> \> \> \> \> M$[(i,j), k, a, b] := 1$;  {\bf $\}$ }\\
\lct  \> \> \> \> \> Counter$[(i,j), k, a, b]$ := Total; \\
\lct  \> \> \> \> \> Prev-Support\=$[(i,j), k, a, b] :=$ \\
\> \> \> \> \> \> $\{ (i,x) | (i,x) \in E \wedge (x=j \vee (j,x) \in E) \wedge (x,k) \in \mbox{Prev-Edge}_{k} \}$ \\
\> \> \> \> \> \> $\cup$ $\{(i, k) | (i, k) \in \mbox{Prev-Edge}_{k}\}$ \\ 
\> \> \> \> \> \> $\cup$ $\{(i, \mbox{\rm start}) | (\mbox{\rm start}, k) \in \mbox{Prev-Edge}_{k}\}$; \\ 
\lct  \> \> \> \> \> Next-Support\=$[(i,j), k, a, b] :=$ \\
\> \> \> \> \> \> $\{ (i,x) | (i,x) \in E \wedge (x=j \vee (j,x) \in E) \wedge (k,x) \in \mbox{Next-Edge}_{k} \} $ \\
\> \> \> \> \> \> $\cup$ $\{(i, k) | (k,i) \in \mbox{Next-Edge}_{k}\}$ \\ 
\> \> \> \> \> \> $\cup$ $\{(i, \mbox{\rm end}) | (k, \mbox{\rm end}) \in \mbox{Next-Edge}_{k}\}$; {\bf $\}$}\\ 
\lct  \> \> \> \> Local-Prev-Support\=$[(i,j), a, b]$ :=\\
\> \> \> \> \> $\{ (i,x) | (i,x) \in E \wedge (x=j \vee (j,x) \in E) \wedge (x,i) \in \mbox{Prev-Edge}_{i} \} $ \\
\> \> \> \> \> $\cup$ $\{(i,\mbox{\rm start}) | (\mbox{\rm start},i) \in \mbox{Prev-Edge}_{i}\}$;  \\
\lct  \> \> \> \> Local-Next-Support$[(i,j), a, b]$ :=\\
\> \> \> \> \> $\{(i,x) | (i,x) \in E \wedge (x=j \vee (j,x) \in E) \wedge (i,x) \in \mbox{Next-Edge}_{i} \}$\\
\> \> \> \> \> $\cup$ $\{(i,\mbox{\rm end}) | (i, \mbox{\rm end}) \in \mbox{Next-Edge}_{i}\}$; {\bf $\}$}
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}
}
%\vspace{.1in}
\caption{Initialization of the data structures for MUSE PC-1.}
\ \\
\ \\
\ \\
\label{preprocess_path}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
\initlct
\lct  \vspace{.05in} \={\bf while} \= $List \not = \phi$ {\bf do} \\
\lct  \> \> Pop $[(i,j), k, a, b]$ from $List$; \\
\lct  \> \> {\bf for} \= $(k,c) \in$ S$[(i, j), k, a, b]$ {\bf do} {\bf $\{$ }\\
\lctl{counter-dec2a}  \> \> \> Counter$[(i,k), j, a, c]$ := Counter$[(i,k), j, a, c]-1$; \\
\lctl{counter-dec2b}  \> \> \> Counter$[(k,i), j, c, a]$ := Counter$[(k,i), j, c, a]-1$; \\
%\lct  \> \> \> S$[(i, j), k, a, b]$ := S$[(i, j), k, a, b] - \{(k,c)\}$;\\
%\lct  \> \> \> S$[(k, j), i, c, b]$ := S$[(k, j), i, c, b] - \{(i, a)\}$;\\
\lct  \> \> \> {\bf if} \=  Counter$[(i,k), j, a, c]=0$ $\wedge$ M$[(i,k), j, a, c]=0$ {\bf then} {\bf $\{$ }\\
\lctl{count-list2}  \> \> \> \> $List := List \cup \{[(i, k), j, a, c],[(k,i),j,c,a]\}$; \\
\lct  \> \> \> \> M$[(i,k), j, a, c] := 1$; M$[(k,i), j, c, a] := 1$; {\bf $\}$ $\}$ }\\
\lct \> \> {\sc Update-Support-Sets}($[(i,j), k, a, b]$);  (see Figure \ref{update_dag2}) {\bf $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}}
\caption{Eliminating inconsistent binary constraints in MUSE PC-1.}
\label{muse_csp_path_algorithm}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6in}
\begin{tabbing}
{\sc Upda}\={\sc te-Support-Sets} ($[(i,j), k, a, b]$){\bf $\{$ }\\
\initlct
\lct \> {\bf for} \= $(i,x) \in$ Prev-Support$[(i,j), k, a, b]$ 
$\wedge$ $x \neq j$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm start}$ {\bf do} {\bf $\{$ }\\
\lct \> \> Prev-Support$[(i,j), k, a, b]$ := Prev-Support$[(i,j), k, a, b] - \{(i,x)\}$; \\
\lct \> \> Next-Support$[(i,j), x, a, b]$ := Next-Support$[(i, j), x, a, b] - \{(i,k)\}$; \\
\lctl{next-nul2} \> \> {\bf if} \=Next-Support$[(i,j), x, a, b]=\phi$ $\wedge$ M$[(i,j), x, a, b]=0$ {\bf then} {\bf $\{$ }\\
\lctl{next-list2} \> \> \> $List := List \cup \{[(i,j),x,a,b],[(j,i),x,b,a]\}$; \\
\lct \> \> \> M$[(i,j), x, a, b] := 1$; M$[(j,i), x, b, a] := 1$; {\bf $\}$ $\}$ }\\
\lct \> {\bf for} \= $(i,x)$ $\in$ Next-Support$[(i,j), k, a, b]$
$\wedge$ $x \neq j$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm end}$
{\bf do} {\bf $\{$ }\\
\lct \> \> Next-Support$[(i,j), k, a, b]$ := Next-Support$[(i,j), k, a, b] - \{(i,x)\}$; \\
\lct \> \> Prev-Support$[(i,j), x, a, b]$ := Prev-Support$[(i, j), x, a, b] - \{(i,k)\}$; \\
\lctl{prev-nul2} \> \> {\bf if} \=Prev-Support$[(i,j), x, a, b]=\phi$ $\wedge$ M$[(i,j), x, a, b]=0$ {\bf then} {\bf $\{$ }\\
\lctl{prev-list2} \> \> \> $List := List \cup \{[(i,j),x,a,b],[(j,i),x,a,b]\}$; \\
\lct \> \> \>  M$[(i,j), x, a, b] := 1$; M$[(j,i), x, b, a] := 1$; {\bf $\}$ $\}$ }\\
\lct \> {\bf if} \= $(k,i) \in$ Prev-Edge$_i$ {\bf then}\\
\lctl{dec-local-prev2i} \> \>  Local-Prev-Support$[(i,j), a, b]$ := Local-Prev-Support$[(i,j), a, b]-\{(i,k) \}$; \\
%\lct \> {\bf if} \= $(k,j) \in$ Prev-Edge$_j$ {\bf then}\\
%\lctl{dec-local-prev2j} \> \>  Local-Prev-Support$[(j,i), b, a]$ := Local-Prev-Support$[(j,i), b, a]-\{(j,k) \}$; \\
\lctl{local-prev-nul2} \> {\bf if} \= Local-Prev-Support$[(i,j), a, b]=\phi$ {\bf then} {\bf $\{$ }\\
\lctl{rel-del1}  \> \> $R{\it 2}(i,a,j,b) := 0;$ $R{\it 2}(j,b,i,a) := 0;$\\
\lct  \> \> {\bf for} \= $(i,x) \in$ Local-Next-Support$[(i, j),a, b]$ 
$\wedge$ $x \neq j$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm end}$
{\bf do}  {\bf $\{$ }\\
\lct \> \> \> Local-Next-Support$[(i, j),a, b]$ :=  Local-Next-Support$[(i, j),a, b] - \{(i,x)\}$; \\
\lct  \> \> \> {\bf if} \=  M$[(i, j), x, a, b]=0$ {\bf then} {\bf $\{$ }\\
\lctl{local-prev-list2a} \> \> \> \>  $List := List \cup \{[(i, j), x, a, b],[(j,i),x,b,a]\}$; \\
\lct \> \> \> \>  M$[(i, j), x, a, b] := 1$; M$[(j,i), x, b, a] := 1$;
{\bf $\}$ $\}$ $\}$ }\\
%\lct \> \> {\bf for} \= $(j,x) \in$ Local-Next-Support$[(j, i), b, a]$ 
%$\wedge$ $x \neq i$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm end}$ {\bf do} \\
%\lct \> \> \> {\bf if} \=  M$[(j, i), x, b, a]=0$ {\bf then} {\bf $\{$ }\\
%\lctl{local-prev-list2b} \> \> \> \>  $List := List \cup \{[(j, i), x, b, a],[(i,j),x,a,b]\}$; \\
%\lct \> \> \> \> M$[(j, i), x, b, a] := 1$; M$[(i,j), x, a,b] := 1$; {\bf $\}$ $\}$ }\\
\lct  \> {\bf if} \= $(i,k) \in$ Next-Edge$_i$ {\bf then}\\
\lctl{dec-local-next2i}  \> \>  Local-Next-Support$[(i,j), a, b]$ := Local-Next-Support$[(i,j), a, b]-\{(i,k) \}$; \\
%\lct  \> {\bf if} \= $(j,k) \in$ Next-Edge$_j$ {\bf then}\\
%\lctl{dec-local-next2j}  \> \>  Local-Next-Support$[(j,i), b, a]$ := Local-Next-Support$[(j,i), b, a]-\{ (j,k) \}$; \\
\lctl{local-next-nul2} \> {\bf if} \= Local-Next-Support$[(i,j), a, b]=\phi$  {\bf then} {\bf $\{$ }\\
\lctl{rel-del2}  \> \> $R{\it 2}(i,a,j,b) := 0;$ $R{\it 2}(j,b,i,a) := 0;$\\
\lct  \> \> {\bf for} \= $(i,x) \in$ Local-Prev-Support$[(i, j), a,
b]$ 
$\wedge$ $x \neq j$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm start}$ {\bf do}{\bf $\{$ }\\
\lct  \> \> \> Local-Prev-Support$[(i, j),a, b]$ :=  Local-Prev-Support$[(i, j),a, b] - \{(i,x)\}$; \\
\lct \> \> \> {\bf if} \=  M$[(i, j), x, a, b]=0$ {\bf then} {\bf $\{$ }\\
\lctl{local-next-list2a} \> \> \> \> $List := List \cup \{[(i, j), x, a, b],[(j,i),x,b,a]\}$; \\
\lct \> \> \> \>  M$[(i, j), x, a, b] := 1$; M$[(j,i), x, b, a] := 1$;
{\bf $\}$ $\}$ $\}$ $\}$ }
%\lct \> \> {\bf for} \= $(j,x)$ $\in$ Local-Prev-Support$[(j,i),b,a]$ $\wedge$%$x \neq i$ $\wedge$ $x \neq k$ $\wedge$ $x \neq {\rm start}$ {\bf do} \\
%\lct \> \> \> {\bf if} \=  M$[(j, i), x, b, a]=0$ {\bf then} {\bf $\{$ }\\
%\lctl{local-next-list2b} \> \> \> \>  $List := List \cup \{[(j, i), x, b, a],[(i,j),x,a,b]\}$; \\
%\lct \> \> \> \> M$[(j, i), x, b, a] := 1$; M$[(i,j), x, a,b] := 1$;
%{\bf $\}$ $\}$ }
\end{tabbing}
\end{minipage} \ \\
\ \\
\hline
\end{tabular}
}
\caption{The function {\sc Update-Support-Sets}($[(i,j),k, a, b]$) for MUSE PC-1.}
\label{update_dag2}
\end{figure}

\subsection{The Running Time, Space Complexity, and Correctness of MUSE PC-1}

The  worst-case running time of the routine to initialize the MUSE PC-1 data
structures (in Figure \ref{preprocess_path}) is O$(n^{3}l^{3} + n^{4}l^{2})$,
where $n$ is the number of
nodes in a MUSE CSP and $l$ is the number of labels.  
Given that the number of $(i,j)$ elements in $E$ is O$(n^{2})$ and the
domain size  is O$(l)$, there are 
O$(n^{3}l^{2})$ entries in the Counter array for which to 
determine the number of supporters, requiring
O$(l)$ work; hence, initializing the Counter array requires 
O$(n^{3}l^{3})$ time. Additionally, there are O$(n^{3}l^{2})$ S
sets to determine, each with O$(l)$ values, so
the time required to initialize them is O$(n^{3}l^{3})$.
Determining each Prev-Support$[(i,j),k,a,b]$ and Next-Support$[(i,j),k,a,b]$
requires O$(n)$ time, so the time required to calculate
all Prev-Support and Next-Support sets is O$(n^{4}l^{2})$.
Finally, the time needed to calculate all Local-Next-Support
and Local-Prev-Support sets is  O$(n^{3}l^{2})$ because
there are O$(n^{2}l^{2})$ sets with up to O$(n)$ elements per set.

The worst-case running time for the algorithm which enforces MUSE
path consistency (in Figures \ref{muse_csp_path_algorithm} and \ref{update_dag2}) also operates
in  O$(n^{3}l^{3} + n^{4}l^{2})$ time.
Clearly there are O$(n^{3}l^{2})$ entries in the Counter array to keep track of in the
algorithm.  Each Counter$[(i,j),k,a,b]$  can be at most $l$ in magnitude, and it can
never become negative, so the maximum running time for lines
\ref{counter-dec2a} and \ref{counter-dec2b} 
in Figure \ref{muse_csp_path_algorithm} (given that elements, because of M, appear on the list only once)
is O$(n^{3}l^{3})$.  Because there are O$(n^{3}l^{2})$ Prev-Support
and Next-Support lists, each up to O$(n)$ in size, the maximum running time
required to eliminate O$(n)$ elements from those support sets is O$(n^{4}l^{2})$.  Finally, since there are
O$(n^{2}l^{2})$ Local-Next-Support and Local-Prev-Support sets from
which to eliminate
O$(n)$ elements, the  worst-case time to eliminate items from the
local sets is O$(n^{3}l^{2})$.  Hence, the  worst-case running time of the MUSE CSP path consistency
algorithm is O$(n^{3}l^{3} + n^{4}l^{2})$.  

The space complexity of MUSE CSP PC-1 is also O$(n^{3}l^{3} + n^{4}l^{2})$
because the arrays Counter and M contain O$(n^{3}l^{2})$ elements and
there are  O$(n^{3}l^{2})$ S sets, each containing O$(l)$ items;
O$(n^{3}l^{2})$ Prev-Support and Next-Support sets, each containing O$(n)$ items; and
O$(n^{2}l^{2})$ Local-Next-Support and Local-Prev-Support sets, each containing 
O$(n)$ items.

By comparison, the worst-case running time and space complexity for
CSP path consistency, PC-4, is O$(n^{3}l^{3})$.  Note that for applications where $\Sigma$ is
representable as planar DAG  or $l=n$, the worst-case running times of
the algorithms are the same order.  If we compare MUSE CSP
to the use of multiple CSPs for problems where
are $k$ alternative variables for a particular variable in a
CSP,  then MUSE CSP path consistency can be asymptotically more
attractive, as shown in Table \ref{table2}.  

\begin{table*}[t]
\renewcommand{\baselinestretch}{.80}
\begin{center}
\begin{tabular}{@{\hspace{0in}}|c@{\hspace{0.05in}}||c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|c@{\hspace{0.05in}}|}
\hline

\vspace*{-.05in}Approach \ & Nodes & Degree of  & Number of & Number of &
Asymptotic\\
\ & per Path  & Node splitting & Constraint Networks & Nodes & Time\\
\hline
\hline
 CSPs &       $n$       &       $k$       &      $k^{n}$      &  $n$  &
$k^{n}n^{3}l^{3}$     \\
\hline
 MUSE CSP &   $n$       &       $k$       &       1       &     $kn$      &
$(kn)^{3}l^{3} + (kn)^{4}l^{2}$  \\
\hline
\end{tabular}
\end{center}
\caption{Comparison of the space and time complexity for MUSE path consistency
on a MUSE CSP to  path consistency on multiple CSPs representing a
node splitting problem (e.g., lexical ambiguity in parsing).}
\label{table2}
\end{table*}

Because the proof of correctness for MUSE PC-1 is similar to our proof
for MUSE AC-1, we will only briefly outline the proof here. 
A binary constraint looses support in MUSE PC-1 (see
lines \ref{rel-del1} and \ref{rel-del2} in Figure \ref{update_dag2})
only if its Local-Prev-Support set or its Local-Next-Support set
becomes empty (see lines \ref{local-prev-nul2} and \ref{local-next-nul2} in Figure \ref{update_dag2}, respectively).  In
either case, it is inadmissible in any MUSE path
consistent instance. We prove that a constraint's local support sets become empty if
and only if it cannot participate in a MUSE path consistent
instance of MUSE CSP.  This is proven for Local-Next-Support
(Local-Prev-Support follows by symmetry).  Observe that if $R{\it
2}(i,a,j,b)=1$, and all of the nodes which immediately follow $i$ (and
similarly $j$) in the DAG are incompatible with the truth of the constraint, then it
cannot participate in a MUSE path consistent instance.  In line
\ref{dec-local-next2i} of Figure \ref{update_dag2}, $(i,k)$ is removed
from the Local-Next-Support$[(i,j),a,b]$ only after
$[(i,j),k,a,b]$ has been popped off $List$.  The removal of $(i,k)$
from Local-Next-Support$[(i,j),a,b]$ indicates that the segment
containing $i$, $j$, and $k$ does not support $R{\it 2}(i,a,j,b)$.  It
remains to be shown that $[(i,j), k, a, b]$ is put on $List$ only if
$R{\it 2}(i,a,j,b)$ must be false for every segment which contains
$i$, $j$, and $k$.  This can be proven by induction on the number of
iterations of the while loop in Figure \ref{muse_csp_path_algorithm}
(much like the proof for MUSE AC-1).
We must also show that if  $R{\it 2}(i,a,j,b)$ = 1 after MUSE PC-1, then
it is MUSE path consistent.  For  $R{\it 2}(i,a,j,b)$
to be MUSE path consistent, 
there must exist at least one path from {\rm start} to {\rm end} which
goes through nodes $i$ and $j$ such that all nodes $n$ on that path
contain at least one label consistent with the constraint.
This proof would
be similar to the second half of the proof for MUSE AC-1 correctness.
From this, we may conclude that MUSE PC-1 builds the largest MUSE path
consistent structure.  


\section{Combining CSPs into a MUSE CSP}

Problems which have an inherent lattice structure or problems
which can be solved by the node splitting approach are natural areas
of application for MUSE CSP, because an exponential number of CSPs are
replaced by a single instance of MUSE CSP, and the DAG representation
of $\Sigma$ is inherent in the problem.  In this section we discuss DAG
construction for other application areas which would benefit from the
MUSE CSP approach, but for which it is not as obvious how to construct
the DAG.  Any set of CSP problems can be used as the segments of a MUSE
CSP.  For example, Figure \ref{example_bad_sigma} illustrates how two
instances of a CSP can be combined into a single
MUSE CSP.   However, using MUSE CSP for this example would not be the
right choice; node sharing cannot offset the cost of
using the extra MUSE AC-1 data structures.


\begin{figure}
\unitlength=.4pt
\centerline{
\begin{tabular}{r l}
\begin{picture}(218.00,85.00)(156.00,515.00)
\put(186.00,533.00){\makebox(0,0)[cc]{\Large $\sigma_{1}=\{$}}
\put(260.00,533.00){\circle{28}}
\put(260.00,533.00){\makebox(0,0)[cc]{4}}
\put(285.00,517.00){\makebox(0,0)[cc]{\Large ,}}
\put(310.00,533.00){\circle{28}}
\put(310.00,533.00){\makebox(0,0)[cc]{5}}
\put(337.00,533.00){\makebox(0,0)[cc]{\Large $\}$}}
\put(186.00,586.00){\makebox(0,0)[cc]{\Large $\sigma_{2}=\{$}}
\put(260.00,586.00){\circle{28}}
\put(260.00,586.00){\makebox(0,0)[cc]{1}}
\put(285.00,570.00){\makebox(0,0)[cc]{\Large ,}}
\put(310.00,586.00){\circle{28}}
\put(310.00,586.00){\makebox(0,0)[cc]{2}}
\put(335.00,570.00){\makebox(0,0)[cc]{\Large ,}}
\put(360.00,586.00){\circle{28}}
\put(360.00,586.00){\makebox(0,0)[cc]{3}}
\put(387.00,586.00){\makebox(0,0)[cc]{\Large $\}$}}
\end{picture} & 
\ \ \ \ \ \psfig{figure=dagize2.ps,height=.5in} \\
\\
\end{tabular}
}
\caption{An example set of CSP problems which would not be a good
candidate for MUSE CSP because of the lack of node sharing.}
\label{example_bad_sigma}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\unitlength=.4pt
\centerline{
\begin{tabular}{l l}
\begin{picture}(218.00,85.00)(156.00,515.00)
\put(186.00,586.00){\makebox(0,0)[cc]{\Large $\sigma_{1}=\{$}}
\put(260.00,586.00){\circle{28}}
\put(260.00,586.00){\makebox(0,0)[cc]{1}}
\put(285.00,570.00){\makebox(0,0)[cc]{\Large ,}}
\put(310.00,586.00){\circle{28}}
\put(310.00,586.00){\makebox(0,0)[cc]{2}}
\put(337.00,586.00){\makebox(0,0)[cc]{\Large $\}$}}
\put(186.00,533.00){\makebox(0,0)[cc]{\Large $\sigma_{2}=\{$}}
\put(260.00,533.00){\circle{28}}
\put(260.00,533.00){\makebox(0,0)[cc]{1}}
\put(285.00,517.00){\makebox(0,0)[cc]{\Large ,}}
\put(310.00,533.00){\circle{28}}
\put(310.00,533.00){\makebox(0,0)[cc]{3}}
\put(337.00,533.00){\makebox(0,0)[cc]{\Large $\}$}}
\put(186.00,480.00){\makebox(0,0)[cc]{\Large $\sigma_{3}=\{$}}
\put(260.00,480.00){\circle{28}}
\put(260.00,480.00){\makebox(0,0)[cc]{2}}
\put(285.00,464.00){\makebox(0,0)[cc]{\Large ,}}
\put(310.00,480.00){\circle{28}}
\put(310.00,480.00){\makebox(0,0)[cc]{3}}
\put(337.00,480.00){\makebox(0,0)[cc]{\Large $\}$}}
\end{picture} 
& 
\psfig{figure=extra_segs3.ps,height=.8in} \\
\\
\end{tabular}
}
\caption{An example of how maximal node sharing leads to spurious
segments.  The first DAG contains two paths, \{1,2,3\} and \{2\}, which correspond
with none of the segments. The second DAG presents a preferred sharing
as created by the {\sc Create-DAG}  routine.}
\label{extra_segs}
\end{figure}

Multiple nodes which have the same name in various CSPs can potentially be
represented as a single node in a MUSE CSP.
We assume that if two nodes, $k_{1}$ and $k_{2}$ are given
the same name (say $k$) in two instances of CSP, then they have the
same domain and obey the same constraints, i.e.:
\begin{enumerate}
\item $L_{k_{1}}= L_{k_{2}}$ (i.e., their domains are equal.)
\item $R1(k_{1},a)=R1(k_{2},a)$ for every $a \in L_{k_1},L_{k_2}$
(i.e., their unary constraints are the same.)
\item $R2(k_{1},a,i,b)=R2(k_{2},a,i,b)$ for labels $a \in L_{k_{1}},
L_{k_{2}}$ and $b \in L_i$, where $i$ is in both segments (i.e., their
binary constraints are the same.)
\end{enumerate}
\noindent However, as illustrated in
Figure \ref{extra_segs}, too much sharing of common nodes can introduce additional
segments that do not appear in the original list of CSPs.  Because the
extra segments can cause extra work to be done,  
it is often desirable to create a DAG which shares nodes 
without introducing extra segments. The algorithm {\sc Create-DAG},
shown in Figure \ref{create_the_dag_code} takes an arbitrary set of
CSP problems as input (a list of segments), and outputs a DAG
representation for those CSPs which shares nodes without
introducing spurious segments.  {\sc Create-DAG} calls an auxiliary
procedure {\sc Order-Sigma} defined in Figure
\ref{ordering_code}. The data structures used in these two routines are
defined in Figure \ref{notation_create}.



\begin{figure}
\tabcolsep .05in
\renewcommand{\baselinestretch}{.85}
\tabcolsep .05in
\centerline{\small
\begin{tabular}{|c|l|}
\hline
\multicolumn{1}{|c} {\bf \ \ \ Notation\ \ \ } & 
\multicolumn{1}{|c|} {\bf Meaning
\begin{tabular}{l}
\ \\
\ \\
\end{tabular}
} \\
\hline
$\Sigma$ &
\begin{tabular}{l}
A set of node sets.  Each node set represents a CSP.
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$\sigma$ &
\begin{tabular}{l}
$\sigma$ is a node set or segment in $\Sigma$.  Each $\sigma$ set is modified to
include\\
{\rm begin} and {\rm end} nodes for the {\sc Create-DAG} algorithm to work\\
properly. Note that $\sigma[0]$ is always the {\rm start} node, and
$\sigma[|\sigma|-1]$ is\\
always the {\rm end} node. Each node $\sigma[pos]$ is a structure with
a name\\ 
and a next-set (names of nodes that follow the node in the DAG).\\
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\ \\
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$G$ &
\begin{tabular}{l}
$G$ is the set of node pairs $(i,j)$ such that there exists a\\
directed edge from $i$ to $j$ in the DAG created by {\sc Create-DAG}.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$N$ &
\begin{tabular}{l}
$N$ is the set of nodes that have been placed in the DAG by\\ 
{\sc Create-DAG}.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$Z$ & 
\begin{tabular}{l}
$Z$ is a set of segments to order with respect to node $j$ in\\
{\sc Order-Sigma}.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$j$ &
\begin{tabular}{l}
The node $j$ is used in {\sc Order-Sigma} to order the remaining\\ 
elements which are smaller than that node.\\
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$U$ & 
\begin{tabular}{l}
$U$ is a set of nodes already considered in the current call to\\
{\sc Order-Sigma}.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$R$ & 
\begin{tabular}{l}
$R$ is a set of nodes in $Z$ in {\sc Order-Sigma}.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
$i$ &
\begin{tabular}{l}
The node $i$ is the largest node which is smaller than $j$ in $R-U$\\ 
(if non-empty) or $R$ in {\sc Order-Sigma}.\\
\end{tabular}
\begin{tabular}{l}
\ \\
\ \\
\ \\
\end{tabular} \\
\hline
$S$ & 
\begin{tabular}{l}
In {\sc Order-Sigma}, $S$ is a set of segments in $Z$ which contain node $i$.\\
\end{tabular} 
\begin{tabular}{l}
\ \\
\ \\
\end{tabular} \\
\hline
\end{tabular}
}
\caption{Data structures used in {\sc Create-DAG} and {\sc Order-Sigma}.}
\label{notation_create}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6.2in}
\begin{tabbing}
{\sc Create}\={\sc -DAG} $()$ {\bf \{ }\\
\initlct
\lct \> Add {\rm start\/} as the first node and {\rm end\/} as the last node for every segment in $\Sigma$;\\
\lct \> {\sc Order-Sigma}($\Sigma$, {\rm start}); \\
\lctl{for} \> {\bf for} \= {\rm pos} := 1 {\bf to} maximum segment length {\bf \{ }\\
\lct \> \> $\Sigma'$ := copy($\Sigma$);\\
\lct \> \> {\bf for} \= $\sigma \in \Sigma' \wedge |\sigma|-1 > {\rm pos}$ {\bf \{ }\\
\lct \> \> \> {\bf if} \= $\sigma[{\rm pos}]$.name = {\rm end\/} {\bf then} {\bf \{ }\\
\lct \> \> \> \>  $G := G \cup \{ (\sigma[{\rm pos}-1]$, $\sigma[{\rm pos}$])$\}$; {\bf \} }\\
\lct \> \> \> {\bf else} \= {\bf \{ }\\
\lct \> \> \> \> SAME\_EDGE\_SET $:=$  $\{\sigma\mbox{1} | $ \= $\sigma\mbox{1}[{\rm pos}-1]$.name = $\sigma[{\rm pos}-1]$.name $\wedge$\\
\> \> \> \> \>  $\sigma\mbox{1}[{\rm pos}]$.name = $\sigma[{\rm pos}]$.name$\}$;\\
\lct \> \> \> \> next-set := $\{\sigma[{\rm pos}+1]$.name $| \sigma$ $\in$  SAME\_EDGE\_SET$\}$;\\
\lct \> \> \> \> $\Sigma'$ := $\Sigma'$ $-$ SAME\_EDGE\_SET; \\
\lct \> \> \> \> {\bf if} \= a node with $\sigma[{\rm pos}]$.name is not in $N$ {\bf then} {\bf \{ }\\
\lct \> \> \> \> \> $N := N \cup \sigma[{\rm pos}]$;\\
\lct \> \> \> \> \> $\sigma[{\rm pos}]$.next := next-set; \\
\lct \> \> \> \> \> $G$ $:=$ $G$ $\cup$ $\{(\sigma[{\rm pos}-1]$, $\sigma[{\rm pos}])\}$; {\bf \} } \\
\lct \> \> \> \> {\bf else} {\bf \{ }\\
\lct \> \> \> \> \> node := get the node in $N$ with the name $\sigma[{\rm pos}]$.name;\\
\lct \> \> \> \> \> {\bf if} \= node.next = next-set  {\bf then} {\bf \{}\\
\lct \> \> \> \> \> \>   $G := G \cup \{(\sigma[{\rm pos}-1], \sigma[{\rm pos}])\}$; {\bf \} } \\
\lct \> \> \> \> \> {\bf else} {\bf \{ }\\
\lct \> \> \> \> \> \> new-node : = Create a new node;\\
\lct \> \> \> \> \> \> new-node.name :=  concatenate($\sigma[{\rm pos}]$.name, '); \\ 
\lct \> \> \> \> \> \> node := get the node in $N$ named new-node.name (if there is one);\\
\lct \> \> \> \> \> \> {\bf while} \= node $\&\&$ node.next !=next-set {\bf do} {\bf \{ }\\
\lct \> \> \> \> \> \> \> new-node.name := concatenate(new-node.name, '); \\   
\lct \> \> \> \> \> \> \> node := get the node in $N$ named new-node.name (if there is one); {\bf \} }\\
\lct \> \> \> \> \> \> {\bf if} \= (node = NULL) {\bf then}\\
\lct \> \> \> \> \> \> \>  $N$ := $N$ $\cup$ {\rm new-node}; \\
\lct \> \> \> \> \> \> {\bf else} new-node := node;\\
\lct \> \> \> \> \> \> {\rm new-node}.next := next-set; \\
\lct \> \> \> \> \> \> Replace $\sigma[{\rm pos}]$.name with {\rm new-node}.name in $\sigma[{\rm pos}-1]$.next;\\
\lct \> \> \> \> \> \> $G := G \cup \{(\sigma[{\rm pos}-1], \mbox{new-node}) \}$; \\
\lct \> \> \> \> \> \> Replace every occurance of $\sigma[{\rm pos}]$ at {\rm pos} with new-node\\
\> \> \> \> \> \> \> in all segments of SAME\_EDGE\_SET; {\bf \} \} \} \} \} } \\
\lct \> Eliminate {\rm start\/} and {\rm end\/} from $G$ and from each $\sigma \in \Sigma$;\ {\bf \} }\\
\end{tabbing}
\end{minipage} \\
\hline
\end{tabular}}
\caption{Routine to create a DAG to represent $\Sigma$.}
\label{create_the_dag_code}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1.0}
\centerline{\small
\begin{tabular}{|c|}
\hline
\ \\
\ \begin{minipage}{6.2in}
\begin{tabbing}
{\sc Order}\={\sc -Sigma} $(Z,j)$ {\bf \{ }\\
\initlct
\lct \> $U := \phi$; \\
\lct \> {\bf while} \= $Z \not = \phi$ {\bf $\{$ }\\
\lct \> \> $R := \displaystyle \bigcup_ {\sigma \in Z} \sigma$; \\
\lct \> \> {\bf if} \= $R - U \not = \phi$ {\bf then}\\
\lct \> \> \> $i$ := the ``largest'' node in $R-U$ which is
less than $j$ ; \\
\lct \> \> {\bf else} \\
\lct \> \> \> $i$ := the ``largest'' node in $R$ which is
less than $j$ ; \\
\lct \> \> $S := \{ \sigma | \sigma \in Z \wedge i \in \sigma
\}$ ; \\
\lct \> \> $Z := Z - S$;\\
\lct \> \> {\bf if} $i \neq {\rm end}$ {\bf then} {\bf $\{$ }\\
\lct \> \> \> {\bf for} \=$\sigma \in S$ {\bf $\{$ }\\
\lct \> \> \> \> Put $i$ after $j$ in $\sigma$; \\
\lct \> \> \> \> $U := U \cup \sigma$; {\bf $\}$ }\\
\lct \> \> \> {\sc Order-Sigma}$(S,i)$ {\bf $\}$ }{\bf $\}$ }{\bf $\}$ }\\
\end{tabbing}
\end{minipage} \\
\hline
\end{tabular}}
\caption{The routine to arrange the nodes within the segments for
convenient merging.}
\label{ordering_code}
\end{figure}


To hold the individual segments in $\Sigma$, the routine {\sc Create-DAG} uses a
special data structure for ordered sets which supports some useful
operations.  If $\sigma$ is a segment and $n$ is an integer, then
$\sigma[n]$ is the node at position $n$ in $\sigma$.  $\sigma[0]$ is always the
{\rm start} node, and $\sigma[|\sigma|-1]$ is always the {\rm end}
node.  $\sigma[k..m]$ is the ordered subset of $\sigma$ consisting of
all the nodes in positions $k$ through $m$.  In addition, the ordered
set allows us to insert a node $i$ immediately after any node $j$ which
is already in the set.  Each node $\sigma[pos]$ is a structure with a
name field and a next-set 
field, which is the set of names of nodes that follow the node
$\sigma[pos]$ in a set of segments.

{\sc Create-DAG} begins by adding special purpose {\rm start} and
{\rm end} nodes to each segment.  It then calls the routine {\sc Order-Sigma} 
shown in Figure \ref{ordering_code} to order the
nodes in each segment.   
{\sc Order-Sigma} orders the nodes of each segment 
such that the ones that are the most common tend to occur earlier 
in the set. To order the elements, it uses 
the operator $>$  (i.e., larger than) which is defined on nodes.  
Note that the {\rm start} node is defined to be the ``largest'' node, and the
{\rm end} node  the ``smallest'' node.  In addition, 
$i > j$ means either that $i$ appears in more segments than $j$ does, 
or if they both appear in the same number of segments, then $i$ has
a lower ordinal number than $j$.  Thus the operator $>$ induces a
total ordering on the nodes in $N$.

When {\sc Order-Sigma} is first called by {\sc Create-DAG} it selects the
largest node $i$ which is smaller than the {\rm start} node.  It then constructs
the set $S$, which is a set of those segments containing $i$.  At this point,
the segments in $S$ are ordered such that the start node is first and $i$
is second.  It then calls {\sc Order-Sigma} to order $S$ for nodes smaller
than $i$.  Once the recursive call is done, any segments that were not
in $S$ are considered (i.e., $Z$).  Note that after the first
iteration of the loop, there is a preference to select the
largest node that was not contained in the segments that were ordered
by the recursive call to {\sc Order-Sigma}.  These items are independent of
the ordered segments, and so will not create spurious paths when placed
early in the DAG; however, items that occur in the already ordered
segments, if placed earlier than items that do not occur in the
ordered segments would tend to introduce spurious paths.
The while loop continues until all segments in $\Sigma$ are ordered.
The worst-case running time of {\sc Order-Sigma} is O$(n^2)$, where $n$ is the sum of
the cardinalities of the segments in $\Sigma$.


Once {\sc Order-Sigma} orders the nodes in the segments, {\sc Create-DAG}
begins to construct the DAG, which is represented as a set of nodes
$N$ and a set of directed edges $G$.  The DAG is constructed by going
through each segment beginning with the position of the second element
(the position after start). The for loop on line 3 looks at nodes in a left to right order, one
position at a time, until all the elements of each segment have been added to
$G$.  If a node with a certain name has not already been placed in
$N$ (i.e., the set of nodes already in the DAG being created) then
adding the node to the graph (as well as a directed edge between 
$\sigma[pos-1]$ and $\sigma[pos]$ to $G$) cannot create any spurious paths in the DAG.  On the other hand,
if a node with the same name as $\sigma[pos]$ had already been placed
in $N$, then it is possible that the current segment
could add paths to the DAG that do not correspond to any of the segments
in $\Sigma$.  To avoid adding spurious segments, we deal with all
segments at one time that share the same previous node 
and have a node with the same
name at the current position.  The basic idea is to add that edge only
once and to keep track of all nodes that can follow that node in
the DAG.  By doing this, we can easily determine whether that same
node can be used if it occurs in another segment in a later position.
The same node can be used only if it is followed by precisely the same set of
next nodes that follow the node already placed in the graph; otherwise,
the second node would have to be renamed to avoid adding spurious segments.  
In such an event, we create a new name for the node.

Note that once the DAG is complete, we eliminate the 
{\rm start} and {\rm end} nodes from $G$ (and their corresponding outgoing and
incoming edges) to make $G$ consistent with its use in the MUSE 
arc consistency and MUSE path consistency algorithms. 
The running time of {\sc Create-DAG} is also O$(n^2)$, where $n$ is the sum of
the cardinalities of the segments in $\Sigma$.

Even though the DAGs produced by the routine {\sc Create-DAG} do have
nice properties, this routine should probably be used only as a
starting point for custom combining routines which are specific to the
intended application area.  We believe that domain-specific
information can play an important role in MUSE combination.  An
example of a domain specific combining algorithm is presented in
\cite{icassp93}, which describes a spoken-language parsing
system which uses MUSE CSP.  A distinguishing feature of this
application's combining algorithm is that instead of avoiding the
creation of extra segments, it allows controlled introduction of extra
segments  because the extra segments often represent sentences
which an N-Best sentence spoken language recognition system would miss. 


\section{Conclusion}

In conclusion, MUSE CSP can be used to efficiently represent 
several similar instances of the constraint satisfaction problem
simultaneously.  If multiple instances of a CSP have some common
variables with the same domains and compatible constraints, then
they can be combined into a single instance of a MUSE CSP, and much of
the work required to enforce node, arc, and path consistency need not be
duplicated across the instances, especially if the constraints are
sufficiently tight.

We have developed a MUSE CSP constraint-based parser, {\sc PARSEC}
\cite{speech-paper,icassp93,icslp}, which is capable of
parsing word graphs containing multiple sentence hypotheses.  We have
developed syntactic and semantic constraints for parsing 
sentences, which when applied to a word graph, eliminate those
hypotheses that are syntactically or semantically incorrect.  For our
work in speech processing, the MUSE arc consistency algorithm is very
effective at pruning the incompatible labels for the individual CSPs
represented in the composite structure. When extracting each of the parses for 
sentences remaining in the MUSE CSP after MUSE
AC-1,  it is usually unnecessary to enforce arc consistency on the CSP represented by
that directed path through the network because of the tightness of 
the syntactic and semantic constraints.

Speech processing is not the only area where segmenting the
signal into higher-level chunks is problematic.  Vision systems and
handwriting analysis systems have comparable problems. In addition,
problems that allow for parallel alternative choices for the type of a
variable, as in parsing lexically ambiguous sentences, are also excellent candidates for MUSE CSP.

C++ implementations of the algorithms described in this paper are
available at the following location:
ftp://transform.ecn.purdue.edu/pub/speech/harper\_code/.
This directory contains a README file and a file called muse\_csp.tar.Z.

\newpage
\acks{This work was supported in part by the Purdue Research
Foundation and a grant from Intel Research Council. We would like to thank
the anonymous reviewers for their insightful recommendations
for improving this paper.}


\bibliographystyle{theapa}
\bibliography{muse}

\end{document}











