\documentstyle[jair,twoside,11pt,theapa,leqno,epsf,amstex]{article}

\jairheading{10}{1999}{199-241}{9/98}{4/99}
\ShortHeadings{Probabilistic Deduction with Conditional Constraints over Basic Events}{Lukasiewicz}
\firstpageno{199}

\overfullrule=2pt

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{satz}{Theorem}[section]
\newtheorem{Lemma}[satz]{Lemma}
\newtheorem{Proposition}[satz]{Proposition}
\newtheorem{Prop}[satz]{Assumption}
\newtheorem{defi}[satz]{Definition}
\newtheorem{bem}[satz]{Remark}
\newtheorem{alg}[satz]{Algorithm}
\newtheorem{bsp}[satz]{Example}

\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bt}{\begin{tabular}}
\newcommand{\et}{\end{tabular}}
\newcommand{\ba}{\begin{alg} \rm}
\newcommand{\ea}{\end{alg}}
\newcommand{\bso}{\begin{satz}}
\newcommand{\eso}{\end{satz}}
\newcommand{\ble}{\begin{Lemma}}
\newcommand{\ele}{\end{Lemma}}
\newcommand{\blew}[1]{\begin{Lemma}[#1]}
\newcommand{\elew}{\end{Lemma}}
\newcommand{\bprop}{\begin{Proposition}}
\newcommand{\eprop}{\end{Proposition}}
\newcommand{\bpropw}[1]{\begin{Proposition}[#1]}
\newcommand{\epropw}{\end{Proposition}}
\newcommand{\bp}{\begin{Prop}}
\newcommand{\ep}{\end{Prop}}
\newcommand{\bdo}{\begin{defi} \rm}
\newcommand{\edo}{\end{defi}}
\newcommand{\bs}[1]{\begin{satz}[#1]}
\newcommand{\es}{\end{satz}}
\newcommand{\bd}[1]{\begin{defi}[#1] \rm}
\newcommand{\ed}{\end{defi}}
\newcommand{\bbsw}[1]{\begin{bsp}[#1] \rm}
\newcommand{\ebsw}{\end{bsp}}
\newcommand{\bb}{\begin{bem} \rm}
\newcommand{\eb}{\end{bem}}
\newcommand{\bbs}{\begin{bsp} \rm}
\newcommand{\ebs}{\end{bsp}}
\newcommand{\beq}{\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
\newcommand{\baq}{\begin{array}}
\newcommand{\eaq}{\end{array}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\bema}{\be}
\newcommand{\ema}{\ee}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%eepicfig.tex
\begingroup\makeatletter
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17 \tiny\else \ifnum #1<20 \small\else
  \ifnum #1<24 \normalsize\else \ifnum #1<29 \large\else
  \ifnum #1<34 \Large\else \ifnum #1<41 \LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@ \count@25 \fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}
\fi
\endgroup

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\arraystretch}{1.3}

\def\ora#1{\overrightarrow{#1}}
\def\ola#1{\overleftarrow{#1}}
\def\urule#1#2#3{(#3|#1)[#2]}
\def\ol#1{\overline{#1}}
\def\Pr{{\it Pr}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Probabilistic Deduction with\\ Conditional Constraints over Basic Events}

\author{\name Thomas Lukasiewicz \email lukasiewicz@@informatik.uni-giessen.de\\
\addr Institut f\"ur Informatik, Universit\"at Gie\ss{}en\\
Arndtstra\ss{}e 2, D-35392 Gie\ss{}en, Germany}

\maketitle

\vspace*{0.5ex}
\begin{abstract}
We study the problem of probabilistic deduction with 
conditional constraints over basic events.
We show that globally complete probabilistic deduction with 
conditional constraints over basic events is NP-hard. 
We then concentrate on the special case of probabilistic deduction in conditional constraint trees.
We elaborate very efficient techniques for globally complete probabilistic deduction. In detail,
for conditional constraint trees with point probabilities, we present a local approach to 
globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees.
For conditional constraint trees with interval probabilities, we show that globally complete probabilistic deduction 
can be done in a global approach by solving nonlinear programs. We show how these nonlinear 
pro\-grams can be transformed into equivalent linear programs, which are solvable in po\-ly\-nomial time 
in the size of the conditional constraint trees. 
\end{abstract}

\vspace*{0.5ex}
\section{Introduction}

Dealing with uncertain knowledge plays an important role in knowledge representation and reasoning.
There are many different formalisms and methodologies for handling uncertainty.
Most of them are directly or indirectly based on probability theory.

In this paper, we focus on probabilistic deduction with 
conditional constraints over basic events 
(that is, interval restrictions for conditional probabilities of elementary events). 
The considered probabilistic deduction problems consist of a 
probabilistic knowledge base and a probabilistic query. We give a classical example.
As a probabilistic knowledge base, we may take the probabilistic knowledge that all 
ostriches are birds, that the probability of Tweety being a bird is greater than 0.90, 
and that the probability of Tweety being an ostrich provided she is a bird is greater 
than 0.80. As a probabilistic query, we may now wonder about the entailed greatest lower 
and least upper bound for the 
probability that Tweety is an ostrich. The solution to this probabilistic deduction 
problem is 0.72 for the entailed greatest lower bound and 1.00 for the entailed least upper bound.

More generally, probabilistic deduction with conditional constraints over propositional events
can be done in a global approach by linear programming or in a local approach by the iterative 
application of inference rules. Note that it is immediately NP-hard, since it generalizes the  
satisfiability problem for classical propositional logic (see Section~\ref{SSCC}).

Research on the global approach spread in particular after the important work
on probabilistic logic by Nilsson (1986) (see also the work by Paa\ss{}, 1988). 
The main focus was on analyzing the computational complexity of satisfiability
and entailment in probabilistic logic and on developing efficient linear programming 
algorithms for these problems. Georgakopoulos et al.\ (1988) 
show that the satisfiability problem in probabilistic logic is NP-complete and
propose to apply column generation techniques for its processing.
This approach was further developed by Kavvadias and Papadimitriou (1990), 
Jaumard et al.\ (1991), Andersen and Hooker (1994), and Hansen et al.\ (1995). 
In particular, Jaumard et al.\ (1991) report promising experimental results on 
the efficiency in special cases of probabilistic satisfiability and entailment. 
Moreover, Kavvadias and Papadimitriou (1990) and 
Jaumard et al.\ (1991) identify special cases of probabilistic satisfiability
that can be solved in polynomial time.
Other work on the global approach concentrates on reducing the number of 
linear constraints (Luo et al.\ 1996) and the number of
variables (Lukasiewicz, 1997).
Finally, Fagin et al.\ (1992) present a sound and complete 
axiom system for reasoning about probabilities that are expressed by 
linear inequalities over propositional events. They show that the 
satisfiability problem in this quite expressive framework is still NP-complete. 

In early work, Dubois and Prade (1988) use inference rules to
model default reasoning with imprecise numerical and fuzzy quantifiers. 
For this reason, subsequent research on inference rules 
especially aims at analyzing patterns of human commonsense reasoning
(Dubois et al.\ 1990, 1993; Amarger et al.\ 1991; Th\"{o}ne, 1994; Th\"{o}ne et al.\ 1995). 
Frisch and Haddawy (1994) discuss the use of inference rules for deduction in probabilistic logic.
Recent work on inference rules concentrates on integrating 
probabilistic knowledge into description logics (Heinsohn, 1994)
and on analyzing the interplay between taxonomic and probabilistic 
deduction (Lukasiewicz 1998a, 1999a).

We now summarize the main characteristics of the global and the local approach.

The global approach can be performed within quite rich probabilistic languages (Fagin et al., 1992).
Crucially, probabilistic deduction by linear programming is globally complete
(that is, it really provides the requested tightest bounds entailed by the whole 
probabilistic knowledge base). However, a main drawback of the global approach 
is that it generally does not provide useful explanatory information
on the deduction process. Finally, results on the special-case tractability of global approaches 
are driven by the technical possibilities of linear programming techniques and not by 
the needs of artificial intelligence applications. 
Hence, they do not seem to be very useful in the artificial intelligence context. 

A main advantage of the local approach is that the 
deduced results can be explained in a natural way by
the sequence of applied inference rules 
(Amarger et al.\ 1991; Frisch \& Haddawy, 1994). However, 
the iterative application of inference rules is generally restricted 
to quite narrow probabilistic languages. Moreover, it is very rarely and only within
very restricted languages globally complete (Frisch and Haddawy, 1994,
give an example of globally complete local probabilistic deduction 
in a very restricted framework). Finally, as far as the computational complexity is concerned,
there are very few experimental and theoretical
results on the special-case tractability of local approaches. 

The main motivating idea of this paper is to elaborate efficient local techniques for 
globally complete probabilistic deduction. Inspired by previous work 
on inference rules, we focus our research on the
language of conditional constraints over basic events:

Dubois and Prade (1988) study the chaining of two bidirectional conditional 
constraints over basic events (``quantified syllogism rule'') and some of its special cases.
Dubois et al.\ (1990) additionally discuss
probabilistic deductions about conjunctions of basic events.
Furthermore, they describe the open problem of
probabilistic deduction along a chain of more than two bidirectional 
conditional constraints over basic events. In later work, 
Dubois et al.\ (1993) use a qualitative version of the 
``quantified syllogism rule'' in an approach to reasoning with linguistic quantifiers. 
Amarger et~al.~(1991) propose to apply the ``quantified syllogism rule'' and 
the ``generalized Bayes' rule'' 
to sets of bidirectional conditional constraints over basic  events.
They report promising experimental 
results on the global completeness and the computational complexity of the presented deduction 
technique. However, this deduction technique is generally not globally complete.
Th{\"o}ne (1994) examines trees of bidirectional conditional constraints over basic  events. 
He presents a linear-time deduction technique that is based on a system of inference rules and 
that computes certain logically entailed greatest lower bounds
(in the technical notions of this paper, which will be defined below, tight lower answers 
to conclusion-restricted queries are computed).

As a first contribution of this paper, we show that globally complete probabilistic deduction with
conditional constraints over basic events is NP-hard. It is surprising that this 
quite restricted class of probabilistic deduction problems is still computationally so 
difficult. Hence, it is unlikely that there is an algorithm that efficiently solves all 
probabilistic deduction problems with conditional constraints over basic events.
However, we can still hope that there are efficient special-case, average-case, 
or approximation algorithms.

In this paper, we then elaborate efficient special-case algorithms.
In detail, we concentrate on probabilistic deduction in conditional constraint trees. 
It is an interesting subclass of all probabilistic deduction problems 
with conditional constraints over basic events.
Conditional constraint trees are undirected trees with basic events as nodes and
with bidirectional conditional constraints over basic events as edges between the nodes
(that is, deduction \mbox{in conditional} constraint trees is a generalization of 
deduction along a chain of bidirectional 
conditional constraints over basic events).
Like Bayesian networks, conditional constraint trees represent 
a well-structured probabilistic knowledge base.
Differently from Bayesian networks, they do not encode any
probabilistic independencies.

As a main contribution of this paper, we have the following results. 
For conditional constraint trees with point probabilities, we present functions 
for deducing greatest lower and least upper bounds in linear time in the size of the 
conditional constraint trees. 
Moreover, for conditional constraint trees with interval probabilities, we show that greatest lower
bounds can be deduced in the same way, in linear time in the size of the conditional constraint trees.
However, computing least upper bounds turns out to be computationally more difficult. It
can be done by solving special nonlinear programs. We show how these nonlinear programs can be transformed 
into equivalent linear programs. The resulting linear programs have a number of variables and
inequalities linear and polynomial, respectively, in the size of the conditional constraint trees. Thus,
our way of deducing least upper bounds still runs in polynomial time in the size of the 
conditional constraint trees, since linear programming runs in polynomial time in the size of the linear programs.

Another important contribution of this paper is related to the question whether
to perform probabilistic deduction with conditional constraints
by the iterative application of inference rules or by linear programming.
On the one hand, the idea of inference rules carries 
us to very efficient techniques for globally complete probabilistic deduction in 
conditional constraint trees. In particular, the considered deduction 
problems generalize patterns of commonsense reasoning.   
However, on the other hand, the corresponding proofs of soundness and global 
completeness are technically quite complex. Hence, it seems unlikely that 
the results of this work can be extended to significantly more general probabilistic 
deduction problems. Note that a companion paper (1998a, 1999a) reports similar 
limits of the local approach in probabilistic deduction under taxonomic knowledge.

The rest of this paper is organized as follows. In Section~\ref{Sec001}, we formulate the
probabilistic deduction problems considered in this work. Section~\ref{PSAT} focuses on the 
probabilistic satisfiability of conditional constraint trees. Section~\ref{SECPRQ} 
deals with globally complete probabilistic deduction in exact and general conditional constraint trees. 
In Section~\ref{Bayes}, we give a comparison with Bayesian networks. 
Section~\ref{SECC} summarizes the main results of this work. 

\section{Formulating the Probabilistic Deduction Problem}\label{Sec001}

In this section, we introduce the syntactic and semantic notions related to
probabilistic knowledge in general and to conditional constraint trees in particular.

\subsection{Probabilistic Knowledge}\label{Sec01}

Before focusing on the details of conditional constraint trees, we give a general introduction to the kind of
probabilistic knowledge considered in this work. 
We deal with conditional constraints over propositional events. They
represent interval restrictions for conditional probabilities of propositional events. 
Note that the formal background introduced in this section is commonly accepted in the 
literature (see especially the work by Frisch and Haddawy, 1994, for other work 
in the same spirit).

We assume a non\-empty and finite set of {\em basic events} ${\cal B}=\{B_1,B_2,\ldots$$,B_n\}$.
The set of {\em conjunctive events} ${\cal C}_{\cal B}$ is the closure of ${\cal B}$
under the Boolean operation $\wedge$. We abbreviate the conjunctive 
event $C\wedge D$ by ${\it CD}$. The set of {\em propositional events} 
${\cal G}_{\cal B}$ is the closure of ${\cal B}$ under the Boolean operations $\wedge$ and $\neg$.
We abbreviate the propositional events \mbox{$G\wedge H$ and $\neg G$} by ${\it GH}$ and 
$\ol{G}$, respectively. The {\em false event} $B_1\wedge\neg B_1$ and the
{\em true event} $\neg (B_1\wedge\neg B_1)$ are abbreviated by $\bot$ and $\top$, respectively.
{\em Conditional constraints} are expressions of the form
$\urule{G}{u_1,u_2}{H}$ with real numbers $u_1,u_2\in[0,1]$
and propositional events $G$ and $H$. In the conditional constraint 
$\urule{G}{u_1,u_2}{H}$, we call $G$ the {\em premise} and $H$ the {\em conclusion}.

To define probabilistic interpretations of propositional events and of conditional constraints, 
we introduce atomic events and the binary relation $\Rightarrow$ between atomic and propositional
events. The set of {\em atomic events} ${\cal A}_{\cal B}$ is defined by
${\cal A}_{\cal B}=\{{\it E_1 E_2} \cdots E_n\,|\, \mbox{$E_i=B_i$}$ $\text{or }
E_i=\ol{B}_i\text{ for all }i\in[1\!:\!n]\}$.
Note that each atomic event can be interpreted as a possible world
(which corresponds to a mapping from ${\cal B}$ to $\{\text{\bf true},\text{\bf false}\}$).
For all atomic events $A$ and all propositional events $G$, let 
$A\Rightarrow G$ iff $A\ol{G}$ is a propositional contradiction.

A {\em probabilistic interpretation} ${\it Pr}$ is a mapping from
${\cal A}_{\cal B}$ to $[0,1]$ such that 
all ${\it Pr}(A)$ with $A\in {\cal A}_{\cal B}$ sum \mbox{up to 1}. 
${\it Pr}$ is extended in a well-defined way 
to propositional events $G$ by:
${\it Pr}(G)$ is the sum of all ${\it Pr}(A)$ with $A\in {\cal A}_{\cal B}$ and $A\Rightarrow G$.
%=\sum_{A\in {\cal A}_{\cal B},\,A\Rightarrow G} {\it Pr}(A)$.
${\it Pr}$ is extended to  conditional constraints by: 
\mbox{${\it Pr}\models\urule{G}{u_1,u_2}{H}$} iff 
$u_1\cdot {\it Pr}(G)\le {\it Pr}({\it GH})\le u_2\cdot {\it Pr}(G)$.

Note that conditional constraints characterize conditional probabilities of events, rather than 
{\em probabilities of conditional events} (Coletti, 1994; Gilio \& Scozzafava, 1994).
Note also that ${\it Pr}(G)=0$ always entails ${\it Pr}\models\urule{G}{u_1,u_2}{H}$.
This semantics of conditional probability statements is also assumed by
Halpern (1990) and by Frisch and Haddawy (1994).

The notions of models, satisfiability, and logical consequence for conditional constraints 
are defined in the classical way. 
A probabilistic interpretation ${\it Pr}$ is a {\em model} of 
a conditional constraint $\urule{G}{u_1,u_2}{H}$ iff ${\it Pr}\models \urule{G}{u_1,u_2}{H}$.
${\it Pr}$ is a {\em model} of a set of conditional constraints ${\it KB}$, denoted ${\it Pr}\models {\it KB}$, 
iff ${\it Pr}$ is a model of all $\urule{G}{u_1,u_2}{H}\in{\it KB}$.
${\it KB}$ is {\em satisfiable} iff a model of ${\it KB}$ exists. $\urule{G}{u_1,u_2}{H}$ is a {\em logical 
consequence} of ${\it KB}\!,$ denoted ${\it KB}\models \urule{G}{u_1,u_2}{H}$, iff each model of ${\it KB}$ is 
also a model of $\urule{G}{u_1,u_2}{H}$.

For a conditional constraint $\urule{G}{u_1,u_2}{H}$ and a set of conditional constraints ${\it KB}$,
let $\boldsymbol{u}$ denote the set of all real numbers $u\in[0,1]$ for which there exists a
model ${\it Pr}$ of ${\it KB}$ with $u\cdot {\it Pr}(G)={\it Pr}({\it GH})$ and ${\it Pr}(G)>0$.
%${\it KB}\cup\{\urule{G}{u,u}{H}\}$ with ${\it Pr}(G)>0$.
Now, we easily verify that $\urule{G}{u_1,u_2}{H}$ is a logical consequence of ${\it KB}$ iff
$u_1\le\inf\boldsymbol{u}$ and $u_2\ge\sup\boldsymbol{u}$.

This observation yields a canonical notion of tightness 
for logical consequences of conditional constraints. 
The conditional constraint 
$\urule{G}{u_1,u_2}{H}$ is a {\em tight logical consequence}
of ${\it KB}\!,$ denoted ${\it KB}\models_{\mbox{\footnotesize {\it tight}}}\urule{G}{u_1,u_2}{H}$, 
iff $u_1=\inf\boldsymbol{u}$ and $u_2=\sup\boldsymbol{u}$.

The set $\boldsymbol{u}$ is a closed interval in the real line (Frisch \& Haddawy, 1994).
Note that for $\boldsymbol{u}=\emptyset$, we canonically define $\inf\boldsymbol{u}=\max\,[0,1]=1$ and 
$\sup\boldsymbol{u}=\min\,[0,1]=0$. 
Thus, $\boldsymbol{u}=\emptyset$ iff ${\it KB}{}\models \urule{\top}{0,0}{G}$ iff
${\it KB}{}\models_{\mbox{\footnotesize {\it tight}}}\urule{G}{1,0}{H}$ iff 
${\it KB}{}\models\urule{G}{u_1,u_2}{H}$ for all $u_1,u_2\in[0,1]$.

Based on the just introduced notion of tight logical consequence, 
probabilistic deduction problems and their solutions are 
more formally specified as follows.

A {\em probabilistic knowledge base} $({\cal B},{\it KB})$ consists of a set of basic events ${\cal B}$
and a set of conditional constraints ${\it KB}$ over ${\cal G}_{\cal B}$ with $u_1\le u_2$
for all $\urule{G}{u_1,u_2}{H}\in {\it KB}$.
A {\em probabilistic query} to a probabilistic knowledge base 
$({\cal B},{\it KB})$ is an expression of the form 
$\exists\urule{E}{x_1,x_2}{F}$ with 
%propositional events 
$E,F\in{\cal G}_{\cal B}$ and two different variables $x_1$ and $x_2$. 
Its {\em tight answer} is the substitution $\sigma=\{x_1/u_1,\,x_2/u_2\}$ 
with $u_1,u_2\in[0,1]$ such that 
${\it KB}\models_{\mbox{\footnotesize {\it tight}}}\urule{E}{u_1,u_2}{F}$
(we call $\sigma_1=\{x_1/u_1\}$ the {\em tight lower answer} and
$\sigma_2=\{x_2/u_2\}$ the {\em tight upper answer}). A {\em correct answer} is a substitution $\sigma=\{x_1/u_1,\,x_2/u_2\}$ 
with $u_1,u_2\in[0,1]$ such that 
${\it KB}\models\urule{E}{u_1,u_2}{F}$.

Finally, we define the notions of soundness and of completeness related to inference rules
and to techniques for probabilistic deduction. An inference rule 
${\it KB}\vdash \urule{G}{u_1,u_2}{H}$ is {\em sound} iff ${\it KB}\models \urule{G}{u_1,u_2}{H}$, 
where $\urule{G}{u_1,u_2}{H}$ is a conditional constraint
and ${\it KB}$ is a set of conditional constraints. It is 
sound and {\em locally complete} iff ${\it KB}\models_{\mbox{\footnotesize {\it tight}}}\urule{G}{u_1,u_2}{H}$.
A technique for probabilistic deduction is {\em sound} for a set of probabilistic queries ${\cal Q}$ 
iff it computes a correct answer to any given
query from ${\cal Q}$. It is sound and \mbox{{\em globally complete} for ${\cal Q}$} iff 
it computes the tight answer to any given query from ${\cal Q}$.

\subsection{Computational Complexity}\label{SSCC}
In the framework of conditional constraints over prop\-o\-si\-tional events, 
the optimization problem of computing the tight answer to a probabilistic query is 
immediately NP-hard, since it
generalizes the satisfiability problem for classical propositional logic
(the NP-complete problem 
of deciding whether a propositional formula in conjunctive normal form is satisfiable;
see especially the survey by Garey and Johnson, 1979).

Surprisingly, the optimization problem of computing the tight answer to a probabilistic query remains NP-hard
even if we just consider conditional constraints over basic events:
\bso
The optimization problem of computing the tight answer to a probabilistic query over basic events that is
directed to a probabilistic knowledge base over basic events is NP-hard.
\eso
{\bf Proof.} The NP-complete decision problem of graph 3-color\-ability 
(Garey \& Johnson, 1979) can be polynomially-reduced to 
the optimization problem of computing the tight answer to a probabilistic query over basic events
that is directed to a probabilistic knowledge base over basic events. The proof follows 
similar lines to the proof of NP-hardness of 2PSAT given by Georgakopoulos et al.\ (1988). 

Let $(V,E)$ be a finite undirected graph. We construct a probabilistic knowledge base
$({\cal B},{\it KB})$ as follows. We initialize $({\cal B},{\it KB})$ with $(\{B\},\emptyset)$.
For each node $v\in V$, we increase ${\cal B}$ by the new basic events $B_v^1$, $B_v^2$, and $B_v^3$. 
For each node $v\in V$ and for each $i\in\{1,2,3\}$, 
we increase ${\it KB}$ by $\urule{B_v^i}{1,1}{B}$ and $\urule{B}{1/3,1/3}{B_v^i}$.
For each node $v\in V$ and for each $i,j\in\{1,2,3\}$ with $i<j$, 
we increase ${\it KB}$ by $\urule{B_v^i}{0,0}{B_v^j}$.
For each edge $\{u,v\}\in E$ and for each $i\in\{1,2,3\}$, 
we increase ${\it KB}$ by $\urule{B_u^i}{0,0}{B_v^i}$. It is easy to see that the probabilistic knowledge base
$({\cal B},{\it KB})$ can be constructed in polynomial time in the size of $(V,E)$.

Now, we show that $(V,E)$ is 3-col\-or\-able iff $\{x_1/1,\,x_2/1\}$ is the tight answer to the 
probabilistic query $\exists\urule{B}{x_1,x_2}{B}$ to $({\cal B},{\it KB})$, or equivalently, iff 
${\it KB}$ is satisfiable: 

If $(V,E)$ is 3-colorable, then 
there exists a mapping $c_1$ from $V$ to $\{1,2,3\}$ with $c_1(u)\neq c_1(v)$ for all edges $\{u,v\}\in E$. 
Thus, if $\pi$ is a cyclic permutation of the members in $\{1,2,3\}$ and if
$c_2,c_3\!:V\rightarrow \{1,2,3\}$ are defined by $c_2(v)=\pi(c_1(v))$ and $c_3(v)=\pi(c_2(v))$ 
for all nodes 
$v\in V$, then also $c_2(u)\neq c_2(v)$ and $c_3(u)\neq c_3(v)$ for all edges $\{u,v\}\in E$. 
For $j\in\{1,2,3\}$, let $A_j\in {\cal A}_{\cal B}$ such that 
$A_j\Rightarrow B$ and $A_j\Rightarrow B_v^i$ iff $c_j(v)=i$ 
for all nodes $v\in V$ and $i\in\{1,2,3\}$. If ${\it Pr}\!:{\cal A}_{\cal B}\rightarrow [0,1]$ 
is defined by ${\it Pr}(A)=1/3$ for all $A\in \{A_1,A_2,A_3\}$ and by ${\it Pr}(A)=0$ for all 
$A\in {\cal A}_{{\cal B}}\setminus\{A_1,A_2,A_3\}$, then ${\it Pr}$ is a model of ${\it KB}$. 

Conversely, if there is a model 
${\it Pr}$ of ${\it KB}$, then there is an atomic event $A\in {\cal A}_{{\cal B}}$ with ${\it Pr}(A)>0$. 
Thus, if $c\!:V\rightarrow \{1,2,3\}$ is defined by $c(v)=i$ iff $A\Rightarrow B_v^i$ for all nodes $v\in V$,
then $c(u)\neq c(v)$ for all edges $\{u,v\}\in E$. Hence, $(V,E)$ is 3-colorable. $\Box$

\medskip
Hence, it is unlikely that there is an efficient algorithm for computing
the tight answer to all probabilistic queries over basic events 
that are directed to any given probabilistic knowledge base over basic events. 
However, there may still be efficient algorithms for solving more specialized 
probabilistic deduction problems. 

The rest of this work deals with probabilistic deduction in conditional constraint trees.
The next section provides a motivating example, which gives evidence of
the practical importance of this kind of probabilistic deduction problems.

\subsection{Motivating Example}\label{sec6ex}

A senior student in mathematics describes her experience about
being successful at the university as follows.
The success of a student ({\sf su}) is influenced by how well-informed ({\sf wi}) and how
well-prepared ({\sf wp}) the student is. Well-informedness can be reached by interviewing 
professors ({\sf pr}) or by asking senior students ({\sf st}). 
Being well-prepared is influenced by how much time is invested in books ({\sf bo}), 
exercises ({\sf ex}), and hobbies ({\sf ho}). 

It is estimated 
that the probability of a student being successful given she is
well-informed lies between 0.60 and 0.70, 
that the probability of a student being well-informed given she is
successful is greater than 0.85,
that the probability of a student being successful given she is 
well-prepared is greater than 0.95,
and that the probability of a student being well-prepared given she is 
successful is greater than 0.95.

This probabilistic knowledge completed by further probabilistic estimations is given by the
probabilistic know\-ledge base $({\cal B},{\it KB})$ in Fig.~\ref{diss16+}, where ${\cal B}$ is
the set of nodes $\{{\sf su, wi, wp, pr,}$ ${\sf st, bo, ex, ho}\}$ and 
${\it KB}$ is the least set of conditional constraints
that contains $\urule{X}{u_1,u_2}{Y}$ for each arrow from $X$ to $Y$
labeled with $u_1,u_2$.
\begin{figure}[h]\vspace*{0.1mm}\vspace*{2ex}
\centerline{\epsfbox{fig01.eps}}
\vspace*{1.5ex}
\caption{\label{diss16+}A Conditional Constraint Tree}\vspace*{1ex}
\end{figure}

We may wonder whether it is useful for being successful at the university to interview the pro\-fessors, 
to study on books, to spend the time on one's hobbies, or to do both studying on books and spending the time
on one's hobbies. This can be expressed by the probabilistic queries
$\exists\urule{{\sf pr}}{x_1,x_2}{{\sf su}}$, $\exists\urule{{\sf bo}}{x_1,x_2}{{\sf su}}$,
$\exists\urule{{\sf ho}}{x_1,x_2}{{\sf su}}$, and $\exists\urule{{\sf bo}\,{\sf ho}}{x_1,x_2}{{\sf su}}$,
which yield the tight answers 
$\{x_1/0.00$, $x_2/1.00\}$, $\{x_1/0.90,x_2/1.00\}$,
$\{x_1/0.30,x_2/0.46\}$, and $\{x_1/0.71,x_2/1.00\}$,
%$[x_1,x_2]=[0.00,1.00]$, $[x_1,x_2]=[0.90,1.00]$, $[x_1,x_2]=[0.30,0.46]$, and $[x_1,x_2]=[0.71,1.00]$, 
respectively. 

We may wonder whether successful students at the university interviewed their professors,
whether they studied on books, whether  they spent their time with their hobbies, or 
whether they both studied on books 
and spent their time with their hobbies. This can be expressed by the probabilistic queries
$\exists\urule{{\sf su}}{x_1,x_2}{{\sf pr}}$, $\exists\urule{{\sf su}}{x_1,x_2}{{\sf bo}}$,
$\exists\urule{{\sf su}}{x_1,x_2}{{\sf ho}}$, and $\exists\urule{{\sf su}}{x_1,x_2}{{\sf bo}\,{\sf ho}}$,
which yield the tight answers 
$\{x_1/0.00$, $x_2/0.17\}$, $\{x_1/0.90,x_2/1.00\}$,
$\{x_1/0.30,x_2/0.45\}$, and $\{x_1/0.25,x_2/0.45\}$,
%$[x_1,x_2]=[0.00,0.17]$, $[x_1,x_2]=[0.90,1.00]$, $[x_1,x_2]=[0.30,0.45]$, and $[x_1,x_2]=[0.25,0.45]$, 
respectively. 

\subsection{Conditional Constraint Trees}\label{SECC1}

We formally define conditional constraint trees and queries to conditional constraint trees.
We provide some additional examples, which are subsequently used as running examples.

A {\em (general) conditional constraint tree} is a probabilistic knowledge base $({\cal B},{\it KB})$ for 
which an undirected tree (a singly connected undirected graph)
$({\cal B},\leftrightarrow)$ exists such that ${\it KB}$ contains exactly one
pair of conditional constraints $\urule{A}{u_1,u_2}{B}$ and $\urule{B}{v_1,v_2}{A}$ with $u_1,v_1>0$
for each pair of adjacent nodes $A$ and $B$ (note that ${\cal B}=\{B\}$ implies ${\it KB}=\emptyset$). 
A basic event $B\in{\cal B}$ is called a {\em leaf} in
$({\cal B},{\it KB})$ iff it has exactly one neighbor in $({\cal B},\leftrightarrow)$.
\mbox{A conditional} constraint tree is {\em exact} iff $u_1=u_2$ 
for all $\urule{A}{u_1,u_2}{B}\in{\it KB}$. 

A {\em query to a conditional constraint tree} is a probabilistic query $\exists\urule{E}{x_1,x_2}{F}$ 
with two conjunctive events $E$ and $F$ that are disjoint in their basic events and such that
all paths from a basic event in $E$ to a basic event \mbox{in $F$} have at least one basic event in common.
\mbox{A query 
$\exists\urule{E}{x_1,x_2}{F}$ to a conditional} constraint tree is {\em prem\-ise-re\-strict\-ed} 
iff $E$ is a basic event.
It is {\em con\-clu\-sion-re\-strict\-ed} iff $F$ is a basic event.
It is {\em strongly con\-clu\-sion-re\-strict\-ed} iff $F$ is the only basic event that is contained in all
paths from a basic event in $E$ to $F$. 
\mbox{It is {\em complete} iff
${\it EF}$ contains exactly the} leaves of $({\cal B},\leftrightarrow)$.

Fig.~\ref{diss53++} shows two conditional constraint trees of which the one on the left side is exact.
$\exists\urule{{\sf MNQR}}{x_1,x_2}{{\sf STU}}$ is a query, while $\exists\urule{{\sf QU}}{x_1,x_2}{{\sf MS}}$ 
is not a query to the conditional constraint trees of Fig.~\ref{diss53++}. Furthermore,
$\exists\urule{{\sf M}}{x_1,x_2}{{\sf STU}}$ is a prem\-ise-re\-strict\-ed query, 
$\exists\urule{{\sf QRSTU}}{x_1,x_2}{{\sf O}}$ a strongly con\-clu\-sion-re\-strict\-ed query, and
$\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$ a prem\-ise-re\-strict\-ed 
complete que\-ry to the conditional constraint trees of Fig.~\ref{diss53++}.

\begin{figure}[ht]\vspace*{0.1mm}
\centerline{\epsfbox{fig02.eps}}   
\vspace*{2ex}     
\caption{\label{diss53++}Two Conditional Constraint Trees}
\end{figure}

For conditional constraint trees $({\cal B},{\it KB})$, conjunctive events $C$, 
and basic \mbox{events \hspace*{-0.2pt}$B$}, 
we write $C$$\,\Rightarrow$$\,B$ iff
there exists a path $G_1,G_2,\ldots$$,G_k$ from a basic event $G_1$ \mbox{in $C$}
to the basic event $G_k$$\,=$$\,B$ such that $\urule{G_{i}}{1,1}{G_{i+1}}$$\,\in$$\,{\it KB}$ for all $i\in[1\!:\!k-1]$. 
We write $B$$\,\Rightarrow$$\,C$ iff
for all paths $G_1,G_2,\ldots$$,G_k$ 
from  the basic event $G_1$$\,=$$\,B$ to a basic event $G_k$ \mbox{in $C$}, it holds  
$\urule{G_{i}}{1,1}{G_{i+1}}$$\,\in$$\,{\it KB}$ for all $i\in[1\!:\!k-1]$. That is, 
the conditions $C$$\,\Rightarrow$$\,B$ and $B$$\,\Rightarrow$$\,C$ immediately entail 
${\it KB}\models (B|C)[1,1]$ and ${\it KB}\models (C|B)[1,1]$, respectively.

Note that the restriction $u_1,v_1>0$ for all
$\urule{A}{u_1,u_2}{B}$, $\urule{B}{v_1,v_2}{A}\in{\it KB}$ 
is just made for technical convenience. The deduction technique of 
Section~\ref{SECPRQ} can easily be generalized to conditional
constraint trees $({\cal B},{\it KB})$ that satisfy only the restriction
$u_1$$\,>$$\,0$ iff $v_1$$\,>$$\,0$ for all
$\urule{A}{u_1,u_2}{B},\urule{B}{v_1,v_2}{A}\in{\it KB}$ (Lukasiewicz, 1996). 


The restriction that for each query $\exists\urule{E}{x_1,x_2}{F}$,
all paths from a basic event in $E$ to a basic event in $F$ have at least one basic event in common 
is crucial for the deduction technique of Section~\ref{SECPRQ}. 
It assures that the problem of computing the tight answer to a complete 
query can be reduced to the problems of computing the tight answer to 
a premise-restricted complete query and the tight answer to 
a strongly conclusion-restricted complete query. 
Note that this restriction is trivially satisfied by all premise- and conclusion-restricted queries 
(for example, by all the queries in Section~\ref{sec6ex}). 

Especially tight answers to conclusion-restricted queries seem to be quite important 
in practice. They may be used to characterize the probability of uncertain basic events
given a collection of basic events that are known with certainty.

\section{Probabilistic Satisfiability}\label{PSAT}

In this section, we show that conditional constraint trees have the nice property that 
they are always satisfiable. That is, within conditional constraint trees, 
the user is prevented from specifying inconsistent probabilistic knowledge.

First, note that conditional constraint trees always have a trivial model in which the probability
of the conjunction of all negated basic events is one and in which the probability of
all the other atomic events is zero. 

The next lemma shows that, given a model ${\it Pr}$ of a conditional constraint tree
and a real number $s$ from $[0,1]$, we can construct a new model 
${\it Pr}_s$ by setting
${\it Pr}_s(A)=s\cdot{\it Pr}(A)$ for all atomic events $A$ that are different from the 
conjunction of all negated basic events. Note that ${\it Pr}_0$ coincides with the trivial model
and that ${\it Pr}_1$ is identical to ${\it Pr}$. This lemma is crucial for inductively
constructing models of conditional constraint trees.

\ble\label{Toll} Let $({\cal B},{\it KB})$ be a conditional constraint tree
with ${\cal B}=\{B_1,B_2,\ldots$$,B_n\}$. Let ${\it Pr}$ be a model of ${\it KB}$ and let $s$
be a real number from $[0,1]$.

The mapping ${\it Pr_s}\colon{\cal A}_{\cal B}\rightarrow [0,1]$ with
${\it Pr_s}(A)=s\cdot{\it Pr}(A)$ for all $A\in{\cal A}_{\cal B}\setminus\{\ol{B}_1 \ol{B}_2 \cdots \ol{B}_n\}$
and ${\it Pr_s}(\ol{B}_1 \ol{B}_2 \cdots \ol{B}_n)=s\cdot{\it Pr}(\ol{B}_1 \ol{B}_2 \cdots \ol{B}_n)-s+1$ is a model of ${\it KB}$.
\ele
%
%
{\bf Proof.} We easily verify that ${\it Pr_s}$ is a probabilistic interpretation.
It remains to show that ${\it Pr_s}$ is also a model of ${\it KB}$. 
Let $\urule{G}{u_1,u_2}{H}\in{\it KB}$. 
Since ${\it Pr}$ is a model of ${\it KB}$, we have ${\it Pr}\models\urule{G}{u_1,u_2}{H}$, hence
$u_1\cdot{\it Pr}(G)\le {\it Pr}({\it GH})\le u_2 \cdot {\it Pr}(G)$, and thus also
$u_1 s\cdot{\it Pr}(G)\le s\cdot {\it Pr}({\it GH})\le u_2 s \cdot {\it Pr}(G)$. 
Since neither $\ol{B}_1 \ol{B}_2 \cdots \ol{B}_n\Rightarrow G$ nor $\ol{B}_1 \ol{B}_2 \cdots \ol{B}_n\Rightarrow {\it GH}$, 
we get $u_1\cdot{\it Pr_s}(G)\le {\it Pr_s}({\it GH})\le u_2\cdot {\it Pr_s}(G)$ and thus 
${\it Pr_s}\models\urule{G}{u_1,u_2}{H}$. $\Box$

\medskip 
Finally, the following theorem shows that conditional constraint trees always have 
a nontrivial model in which all the basic events
have a probability greater than zero.
%
\bso\label{Doll}
Let $({\cal B},{\it KB})$ be a conditional constraint tree with ${\cal B}=\{B_1,B_2,\ldots{},B_n\}$.

There is a model ${\it Pr}$ of ${\it KB}$ with ${\it Pr}(B_1 B_2 \cdots{} B_n)>0$.
\eso
%
%
{\bf Proof.} It is sufficient to show the claim for exact conditional constraint trees.
The claim is proved by induction on the number of basic events.

\medskip
\noindent {\it Basis:} for $({\cal B},{\it KB})=(\{B\},\emptyset)$, a model ${\it Pr}$ of ${\it KB}$ 
with ${\it Pr}(B)>0$ is given by $\ol{B},B\mapsto 0,1$
(note that $\ol{B},B\mapsto 0,1$ is an abbreviation for $\Pr(\ol{B})=0$ and $\Pr(B)=1$).

\medskip
\noindent {\it Induction:} let $({\cal B},{\it KB})=({\cal B}_1\cup {\cal B}_2,{\it KB}_1\cup {\it KB}_2)$ 
with two exact conditional constraint trees $({\cal B}_1,{\it KB}_1)=
(\{B,C\},\{\urule{B}{u,u}{C},\urule{C}{v,v}{B}\})$ and 
$({\cal B}_2,{\it KB}_2)=(\{C,D_1,\ldots{},D_k\},{\it KB}_2)$
such that ${\cal B}_1\cap{\cal B}_2=\{C\}$.
A model ${\it Pr}_1$ of ${\it KB}_1$ with ${\it Pr}_1({\it BC})>0$ is given by:

\begin{displaymath}\mbox{$\ol{B}\,\ol{C},B\ol{C},\ol{B} C,{\it BC}\ \mapsto\ 
\frac{u v}{u+v},\frac{v-u v}{u+v},\frac{u-u v}{u+v},\frac{u v}{u+v}\ .$}\end{displaymath}
By the induction hypothesis, there is a model ${\it Pr}_2$ of ${\it KB}_2$
(that is defined on the atomic events over ${\cal B}_2$) 
with ${\it Pr}_2(C D_1\cdots D_k)$$\,>$$\,0$. By Lemma~\ref{Toll}, we can assume ${\it Pr}_2(C)={\it Pr}_1(C)$. 
A probabilistic interpretation ${\it Pr}$ on the atomic events over ${\cal B}$ is now defined by:
\begin{displaymath}\mbox{$%
{\it Pr}(A_b A_c A_2)\ =\ \frac{{\it Pr}_1(A_b A_c)\cdot{\it Pr}_2(A_c A_2)}{{\it Pr}_2(A_c)}$}\\
\end{displaymath}
for all atomic events  $A_b$, $A_c$, and $A_2$ over $\{B\}$, $\{C\}$, 
and ${\cal B}_2\setminus\{C\}$, respectively. We easily verify that 
${\it Pr}({\it A_b A_c})={\it Pr}_1({\it A_b A_c})$
and ${\it Pr}({\it A_c A_2})={\it Pr}_2({\it A_c A_2})$ for all atomic events  
$A_b$, $A_c$, and $A_2$ over $\{B\}$, $\{C\}$, 
and ${\cal B}_2\setminus\{C\}$, respectively.
Hence, ${\it Pr}$ is a model of ${\it KB}$. Moreover,  ${\it Pr}_1({\it BC})>0$ 
and ${\it Pr}_2(C D_1\cdots D_k)>0$ entails ${\it Pr}(B C D_1\cdots D_k)>0$. $\Box$

\section{Probabilistic Deduction}\label{SECPRQ}
%
In this section, we present techniques for computing 
tight answers to queries directed to exact and general conditional constraint trees,
and we analyze their computational complexity. More precisely, 
the problem of computing the tight answer to a query is reduced to 
the problem of computing the tight answer to a complete query. The latter problem
is then reduced to the problems of computing the tight answer to 
a premise-restricted complete query and the tight answer to 
a strongly conclusion-restricted complete query. 

\subsection{Premise-Restricted Complete Queries}\label{AAAA}
\subsubsection{Exact Conditional Constraint Trees}\label{0GAGA}\label{EXCT}

We now focus on the problem of computing tight answers
to premise-restricted complete queries that are directed to exact conditional constraint trees. 

Let $({\cal B},{\it KB})$ be an exact conditional constraint tree
and let $\exists\urule{E}{x_1,x_2}{F}$ be a premise-restricted complete query.
To compute the tight answer to $\exists\urule{E}{x_1,x_2}{F}$, 
we start by defining a directed tree (that is, a directed acyclic
graph in which each node has exactly one parent, except for the root, which does not have any): 
\begin{center}$\begin{array}{lll}
A\rightarrow B& \text{iff} & \text{$A\leftrightarrow B$ and $A$ is closer to $E$ than $B$.}\\
\end{array}$\end{center}
This directed tree $({\cal B},\rightarrow)$ is uniquely determined by the conditional constraint tree and the premise-restricted complete query.
Fig.~\ref{diss11++} shows $({\cal B},\rightarrow)$ for the premise-restricted complete query 
$\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$ to the exact conditional constraint tree 
in Fig.~\ref{diss53++}, left side.
\begin{figure}[ht]\vspace*{0.1mm}
\centerline{
\epsfbox{fig03.eps}}
\vspace*{3ex}
\caption{\label{diss11++}Directed Tree $({\cal B},\rightarrow)$}
\end{figure}

Now, the set of nodes ${\cal B}$ is partitioned into several strata.
The lowest stratum contains only nodes with no children in $({\cal B},\rightarrow)$, the highest 
stratum contains the nodes with no parents in $({\cal B},\rightarrow)$ (that is, exactly the node 
of the premise $E$ of the query). Fig.~\ref{diss11++} also shows the different strata
in our example.

At each node of $({\cal B},\rightarrow)$, we compute certain tightest bounds 
that are logically entailed by ${\it KB}$. More precisely, the tightest bounds at a node $B$ are 
computed locally, by exploiting the tightest bounds that have previously been computed at the
children of $B$. Hence, we iteratively compute the tightest bounds at the nodes of 
each stratum, starting with the nodes of the lowest stratum and terminating with 
the nodes of the highest stratum. 
We distinguish three different ways of computing tightest bounds at a node:
\begin{itemize}
\item initialization of a leaf ({\sc Leaf}), 
\item chaining of an arrow and a subtree via a common node ({\sc Chaining}),
\item fusion of subtrees via a common node ({\sc Fusion}).
\end{itemize}
%\begin{itemize}
%\item initialization of a leaf ({\sc Leaf}), 
%\item chaining of an arrow and a subtree via a common node ({\sc Chaining}),
%\item fusion of subtrees via a common node ({\sc Fusion}).
%\end{itemize}
Let us consider again the %example of computing the tight answer to the 
premise-restricted 
complete query $\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$
to the exact conditional constraint tree in Fig.~\ref{diss53++}, left side.
Fig.~\ref{diss12-1} illustrates the three different ways of computing tightest bounds at a node
(the common nodes for {\sc Chaining} and {\sc Fusion} are filled black).
Table~\ref{TABlllPPP} shows the greatest lower and the least upper bounds that are computed 
at each node $B$ of each stratum.
More precisely, these bounds are $\alpha_1=\inf {\it Pr}({\it BD})/{\it Pr}({\it B})$, 
$\alpha_2=\sup {\it Pr}({\it BD})/{\it Pr}({\it B})$,
$\beta_2=\sup {\it Pr}({\it \ol{B}D})/{\it Pr}({\it B})$, 
and $\gamma_2=\sup {\it Pr}({\it D})/{\it Pr}({\it B})$
subject to ${\it Pr}\models{\it KB}$ and ${\it Pr}(B)>0$. 
Table~\ref{TABlllPPP} also shows the requested tight answer $\{x_1/0.02,\,x_2/0.17\}$, 
%to the premise-restricted 
%complete query $\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$, 
which is given by the tightest bounds $\alpha_1$ and $\alpha_2$ that are computed 
at the \mbox{premise ${\sf M}$}. %In detail, it is provided by $\{x_1/0.02,\,x_2/0.17\}$.
%\newpage
%\vfill
\begin{figure}\vspace*{5mm}
\centerline{
\epsfbox{fig04.eps}}  
\vspace*{3ex}
\caption{\label{diss12-1}Local Computations in $({\cal B},\rightarrow)$}
\end{figure}

\begin{table}[h]
\vspace*{1ex}\centerline{
\mbox{$\baq{cclccccl}
\hline\\[-3.6ex]
%\text{strata}  & B        & A & \inf\frac{{\it Pr}({\it BA})}{{\it Pr}({\it B})}  & \sup \frac{{\it Pr}({\it BA})}{{\it Pr}({\it B})}  & \sup 
%\frac{{\it Pr}({\it \ol{B}A})}{{\it Pr}({\it B})} &\sup \frac{{\it Pr}({\it A})}{{\it Pr}({\it B})}\\
\!\text{strata}\! & B & D & \alpha_1 & \alpha_2 & \beta_2 & \gamma_2 & \\
\\[-3.6ex]\hline
                    & {\sf S} & {\sf S}     & 1.0000 & 1.0000 & 0.0000 & 1.0000 & ({\sc Leaf})\\[-1.27ex]
                  0 & {\sf T} & {\sf T}     & 1.0000 & 1.0000 & 0.0000 & 1.0000 & ({\sc Leaf})\\[-1.27ex]
                    & {\sf U} & {\sf U}     & 1.0000 & 1.0000 & 0.0000 & 1.0000 & ({\sc Leaf})\\[-0.6ex]
                    & {\sf P} & {\sf S}     & 0.8500 & 0.8500 & 0.0447 & 0.8947 & ({\sc Chaining})\\[-1.27ex]
                  1 & {\sf P} & {\sf T}     & 0.8500 & 0.8500 & 0.0447 & 0.8947 & ({\sc Chaining})\\[-1.27ex]
                    & {\sf P} & {\sf U}     & 0.8500 & 0.8500 & 0.0000 & 0.8500 & ({\sc Chaining})\\[-0.6ex]
                    & {\sf P} & {\sf STU}   & 0.5500 & 0.8500 & 0.0000 & 0.8500 & ({\sc Fusion})\\[-1.27ex]
                  1 & {\sf Q} & {\sf Q}     & 1.0000 & 1.0000 & 0.0000 & 1.0000 & ({\sc Leaf})\\[-1.27ex]
                    & {\sf R} & {\sf R}     & 1.0000 & 1.0000 & 0.0000 & 1.0000 & ({\sc Leaf})\\[-0.6ex]
                    & {\sf O} & {\sf STU}   & 0.4474 & 0.7605 & 0.0447 & 0.7605 & ({\sc Chaining})\\[-1.27ex]
                  2 & {\sf O} & {\sf Q}     & 0.9500 & 0.9500 & 0.0500 & 1.0000 & ({\sc Chaining})\\[-1.27ex]
                    & {\sf O} & {\sf R}     & 0.9500 & 0.9500 & 5.3833 & 6.3333 & ({\sc Chaining})\\[-0.6ex]
                  2 & {\sf O} & {\sf QRSTU} & 0.3474 & 0.7605 & 0.0447 & 0.7605 & ({\sc Fusion})\\[-0.6ex]
                  3 & {\sf N} & {\sf QRSTU} & 0.1911 & 0.4183 & 0.0246 & 0.4183 & ({\sc Chaining})\\[-0.6ex]
                  4 & {\sf M} & {\sf QRSTU} & 0.0169 & 0.1722 & 0.0719 & 0.1722 & ({\sc Chaining})\\\hline
		  \eaq$}}
\vspace*{2.5ex}  
\caption{Locally Computed Tightest Bounds}\label{TABlllPPP}
\vspace*{0.5ex}  
\end{table}

We now focus on the technical details. We present the functions ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$, 
which compute the described greatest lower and least upper bounds.
For this purpose, we need the following definitions.
Let ${\it Pr}({\it C}|B)$ denote $u$ for all $\urule{B}{u,u}{C}\in{\it KB}$.

A node $B$ is a {\em leaf} if it does not have any children. 
For all leaves $B$, let $B^{\uparrow}=B$. 
For all the other nodes $B$, let $B^{\uparrow}$ be the conjunction of all the children of $B$.
For all leaves $C$, let $L(C)=C$. For all the other conjunctive events $C$, let
$L(C)$ be the conjunction of all the leaves that are in $C$ or that are descendants of a node in $C$.

In the sequel, let $B$ be a node and let $C=B^{\uparrow}$. The case $C=B$ refers
to the initialization of the leaf $B$, the case $C=B_1$ with a node $B_1\neq B$ to the chaining of the arrow 
$B\rightarrow B_1$ and a subtree via the common node $B_1$, and 
the case $C={\it B_1 B_2}\ldots B_k$ with $k>1$ nodes $B_1,B_2,\ldots$$,B_k$ to the fusion of $k$ subtrees via the common node $B$.

We define the function ${\it H}^{\alpha}_1$ for computing greatest lower bounds:
let \mbox{${\it H}^{\alpha}_1(B,C)=\alpha_1$} (note that $\alpha_1$
will coincide with the greatest lower bound of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}({\it B})$ 
subject to ${\it Pr}\models{\it KB}$ and ${\it Pr}(B)>0$),
where $\alpha_1$ in {\sc Leaf} ($C=B$), {\sc Chaining} 
($C=B_1$), and {\sc Fusion} ($C={\it B_1 B_2}\ldots B_k$ with $k>1$) is given as follows:

\bigskip
\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\alpha_1 & = & 1\\
\eaq$

\bigskip
\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\alpha_1 & = & \max(0,{\it Pr}({\it C}|B)\cdot(1+\frac{{\it H}^{\alpha}_1(C,\,C^{\uparrow})-1}{{\it Pr}({\it B}\mid C)})) \\
\eaq$

\bigskip
\noindent {\sc Fusion}:

\medskip
$\baq{lll}
\alpha_1 & = & \max(0,1-k+\sum\limits_{i=1}^{k}{\it H}^{\alpha}_1(B,B_i))\\
\eaq$

\bigskip
To express that ${\it H}^{\alpha}_1$ computes greatest lower bounds, we need the following
definitions. Let ${\cal B}(B,C)$ comprise $B$, all nodes in $C$ and all
descendants of a node in $C$. Let ${\it KB}(B,C)$ be the set of all
conditional constraints of ${\it KB}$ over ${\cal B}(B,C)$. Let
${\it Mo}(B,C)$ be the set of all models of ${\it KB}(B,C)$ 
that are defined on the atomic events over ${\cal B}(B,C)$.

Now, the function ${\it H}^{\alpha}_1$ is sound and globally complete with respect to $B$ and $C$ iff 
${\it H}^{\alpha}_1(B,C)=\alpha_1$ is the greatest lower bound of 
${\it Pr}({\it BL(C)})\,/\,{\it Pr}(B)$ subject to ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
Thus, the next theorem shows soundness and global completeness of ${\it H}^{\alpha}_1$.

\bso \label{satzBLB2}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) For all probabilistic interpretations ${\it Pr}\in {\it Mo}(B,C)$, 
it holds $\alpha_1\cdot{\it Pr}(B) \le {\it Pr}(BL(C))$.

\medskip
\noindent b) There exists a probabilistic interpretation ${\it Pr}\in{\it Mo}(B,C)$ with 
${\it Pr}(B)>0$, $\alpha_1\cdot{\it Pr}(B)={\it Pr}({\it BL(C)})$, and $\Pr(\ol{B}L(C))=0$ 
iff $L(C)$$\,\Rightarrow$$\,B$.
\eso
{\bf Proof.} The proof is given in full detail in Appendix B. $\Box$

\medskip
Next, we present the functions ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$
for computing least upper bounds. Note that 
%it has been unknown in the literature so far whether such functions exist.
%These functions 
${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$ show the crucial result that for exact conditional constraint trees, 
there are local probabilistic deduction techniques that are sound and globally complete.

In detail, let ${\it H}^{\alpha}_2(B,C)=\alpha_2$, 
${\it H}^{\beta}_2(B,C)=\beta_2$, and 
${\it H}^{\gamma}_2(B,C)=\gamma_2$ (note that $\alpha_2$, $\beta_2$, and $\gamma_2$
will coincide with the least upper bound of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}({\it B})$, 
${\it Pr}({\it \ol{B}L(C)})\,/\,{\it Pr}({\it B})$, and 
${\it Pr}({\it L(C)})\,/\,{\it Pr}({\it B})$,
respectively, 
subject to ${\it Pr}\models{\it KB}$ and \mbox{${\it Pr}(B)>0$}), where $\alpha_2$, 
$\beta_2$, and $\gamma_2$ 
in {\sc Leaf} ($C=B$), {\sc Chaining} 
($C=B_1$), and {\sc Fusion} ($C={\it B_1 B_2}\ldots B_k$ with $k>1$) are given as follows:

\bigskip
\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\alpha_2 & = & 1\\
\beta_2  & = & 0\\
\gamma_2 & = & 1\\
\eaq$

\bigskip
\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\alpha_2 & = & \min(1,{\it Pr}({\it C}|B)\cdot \frac{{\it H}^{\gamma}_2(C,\,C^{\uparrow})}{{\it Pr}(B|C)},\,
 1-{\it Pr}({\it C}|B)\cdot(1-\frac{{\it H}^{\alpha}_2(C,\,C^{\uparrow})}{{\it Pr}(B|C)}),\\[0.8ex]
 &&\!\!\phantom{\min(}{\it Pr}({\it C}|B)\cdot(1+\frac{{\it H}^{\beta}_2(C,\,C^{\uparrow})}{{\it Pr}(B|C)}))\\[1.5ex]
\beta_2 & = & \min({\it Pr}({\it C}|B)\cdot (\frac{{\it H}^{\beta}_2(C,\,C^{\uparrow})+1}{{\it Pr}(B|C)}-1),\,
{\it Pr}({\it C}|B)\cdot \frac{{\it H}^{\gamma}_2(C,\,C^{\uparrow})}{{\it Pr}(B|C)})\\[1.5ex]
\gamma_2 & = & {\it Pr}({\it C}|B)\cdot \frac{{\it H}^{\gamma}_2(C,\,C^{\uparrow})}{{\it Pr}(B|C)}\\
\eaq$

\bigskip
\noindent {\sc Fusion}:

\medskip
$\baq{lll}
\alpha_2 & = & \min\limits_{i\in[1:k]} {\it H}^{\alpha}_2(B,B_i)\\[1.5ex]
\beta_2 & = & \min\limits_{i\in[1:k]} {\it H}^{\beta}_2(B,B_i)\\[1.5ex]
\gamma_2 & = & \min(\min\limits_{i\in[1:k]}{\it H}^{\gamma}_2(B,B_i),\,
\min\limits_{i,j\in[1:k],i\neq j}({\it H}^{\alpha}_2(B,B_i)+{\it H}^{\beta}_2(B,B_j)))\\
\eaq$

\bigskip
The functions 
${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$ are sound and globally complete with 
respect to $B$ \mbox{and $C$} iff ${\it H}^{\alpha}_2(B,C)=\alpha_2$, 
${\it H}^{\beta}_2(B,C)=\beta_2$, and 
${\it H}^{\gamma}_2(B,C)=\gamma_2$
are the least upper bounds of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}(B)$, ${\it Pr}({\it \ol{B}L(C)})\,/\,{\it Pr}(B)$,
and ${\it Pr}({\it L(C)})\,/\,{\it Pr}(B)$, respectively, subject to ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$. 
Hence, the following theorem shows soundness and global completeness of ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$
(actually, it shows even more to enable a 
proof by induction on the recursive \mbox{definition of ${\it H}^{\alpha}_2$, 
${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$).}
\bso \label{GRAPHU}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) For all probabilistic interpretations ${\it Pr}\in {\it Mo}(B,C)$, it holds 
${\it Pr}(BL(C))\le \alpha_2\cdot{\it Pr}(B)$, ${\it Pr}(\ol{B}L(C))\le \beta_2\cdot{\it Pr}(B)$, 
and ${\it Pr}(L(C))\le \gamma_2\cdot{\it Pr}(B)$.

\medskip
\noindent b) There exists a probabilistic interpretation ${\it Pr}\in {\it Mo}(B,C)$
with ${\it Pr}(B)>0$, ${\it Pr}(BL(C))=\alpha_2\cdot {\it Pr}(B)$, and
${\it Pr}(L(C))=\gamma_2\cdot {\it Pr}(B)$.

\medskip
\noindent c) There exists a probabilistic interpretation ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(B)>0$,
${\it Pr}(\ol{B}L(C))=\beta_2\cdot {\it Pr}(B)$, and ${\it Pr}(L(C))=\gamma_2\cdot {\it Pr}(B)$. 
\eso
{\bf Proof.} The proof is given in full detail in Appendix B. $\Box$  

\medskip
Note that Theorem~\ref{GRAPHU} also shows that ${\it H}^{\gamma}_2(B,B_i)\le {\it H}^{\alpha}_2(B,B_i)+{\it H}^{\beta}_2(B,B_i)$
for all $i\in[1\!:\!k]$. Thus, the expression $\min_{i,j\in[1:k],i\neq j}({\it H}^{\alpha}_2(B,B_i)+{\it H}^{\beta}_2(B,B_j))$ 
in the definition of $\gamma_2$ in {\sc Fusion} can be replaced by $\alpha_2+\beta_2$ for an increased efficiency in computing 
$\gamma_2$ by exploiting the already computed values of $\alpha_2$ and $\beta_2$.

Briefly, by Theorems~\ref{satzBLB2} and \ref{GRAPHU}, 
the tight answer to the premise-restricted complete query $\exists\urule{E}{x_1,x_2}{F}$
is given by $\{x_1/{\it H}^{\alpha}_1(E,E^{\uparrow}),\,x_2/{\it H}^{\alpha}_2(E,E^{\uparrow})\}$.

%The time complexity of computing the tight answer to a 
%premise-re\-stricted complete query this way, by using the 
%functions ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$, 
%is analyzed in Section~\ref{SECTC}. 

\subsubsection{Conditional Constraint Trees}
\label{0SECC3}\label{EXXX}

We now focus on computing the tight answer to premise-restricted 
complete queries to general conditional constraint trees. In the sequel, let
$({\cal B},{\it KB})$ be a conditional constraint tree and 
let $\exists\urule{E}{x_1,x_2}{F}$ be a premise-restricted complete query. 

We may think that the local deduction technique for exact conditional constraint trees of Section~\ref{EXCT}
can easily be generalized to conditional constraint trees. In fact, this is true as far as the computation of greatest lower 
bounds is concerned. However, the computation of least upper bounds cannot be generalized that easily from exact 
conditional constraint trees to conditional constraint trees. More precisely, generalizing the computation of least upper bounds results 
in solving nonlinear programs. These nonlinear programs 
and our way to solve them are illustrated by the following chaining example.

Let the conditional constraint tree $({\cal B},{\it KB})$ 
be given by \mbox{${\cal B}\!=\!\{{\sf M},{\sf N},{\sf O},{\sf P}\}$} and
${\it KB}\!=\!\{\urule{{\sf M}}{u_1,u_2}{{\sf N}},\urule{{\sf N}}{v_1,v_2}{{\sf M}}$, 
$\urule{{\sf N}}{x_1,x_2}{{\sf O}}$, $\urule{{\sf O}}{y_1,y_2}{{\sf N}}$,
$\urule{{\sf O}}{r_1,r_2}{{\sf P}}$, $\urule{{\sf P}}{s_1,s_2}{{\sf O}}\}$.
Let us consider the pre\-mise-restricted complete que\-ry $\exists\urule{{\sf M}}{z_1,z_2}{{\sf P}}$. 

By Theorem~\ref{GRAPHU} and some straightforward arithmetic transformations, the requested least upper bound  is the 
maximum of $z$ subject to $u\in[u_1,u_2]$, $v\in[v_1,v_2]$, $x\in[x_1,x_2]$, $y\in[y_1,y_2]$, $r\in[r_1,r_2]$, 
$s\in[s_1,s_2]$, and the nonlinear inequalities in (\ref{KKK9-B}) to (\ref{KKK9-E}):\vspace*{-0.4ex}
\begin{eqnarray}
\label{KKK9-B}z \!\!&\le&\!\! \mbox{$1$}\\[0.2ex]
z \!\!&\le&\!\! \mbox{$1 -u +\frac{u}{v} -\frac{ux}{v}+\frac{uxr}{vy}$}\\[0.2ex]
z \!\!&\le&\!\! \mbox{$1 -u +\frac{ux}{v} -\frac{uxr}{vy}+\frac{uxr}{vys}$}\\[0.2ex]
z \!\!&\le&\!\! \mbox{$u -\frac{ux}{v} +\frac{ux}{vy}-\frac{uxr}{vy}+\frac{uxr}{vys}$}\\[0.2ex]
\label{KKK9-E}z \!\!&\le&\!\! \mbox{$\frac{uxr}{vys}$}
\end{eqnarray}
In this system of nonlinear inequalities, all upper bounds of $z$ are monotonically decreasing in 
$v$, $y$, and $s$. Hence, we can equivalently maximize $z$ subject to $u\in[u_1,u_2]$, $x\in[x_1,x_2]$, 
$r\in[r_1,r_2]$, and the nonlinear inequalities in (\ref{BKKK9-1}) to (\ref{BKKK9-5}):\vspace*{-0.4ex}
\begin{eqnarray}
\label{BKKK9-1}z \!\!&\le&\!\! \mbox{$1$}\\[0.2ex]\label{eqq1}
\label{BKKK9-2}z \!\!&\le&\!\! \mbox{$1 -u +\frac{u}{v_1} -\frac{ux}{v_1 }+\frac{uxr }{v_1 y_1 }$}\\[0.2ex]\label{eqq2}
\label{BKKK9-3}z \!\!&\le&\!\! \mbox{$1 -u +\frac{ux}{v_1 } -\frac{uxr}{v_1 y_1 }+\frac{uxr }{v_1 y_1 s_1 }$}\\[0.2ex]
\label{BKKK9-4}z \!\!&\le&\!\! \mbox{$u -\frac{ux}{v_1 } +\frac{ux}{v_1 y_1 }-\frac{uxr }{v_1 y_1 }+\frac{uxr }{v_1 y_1 s_1 }$}\\[0.2ex]
\label{BKKK9-5}z \!\!&\le&\!\! \mbox{$\frac{uxr }{v_1 y_1 s_1}$}
\end{eqnarray}
For example, the requested least upper bound for $u_1=u_2=u$ and $x_1=x_2=x$ is shown
in Fig.~\ref{diss13} for $u,x\in[0,1]$, $r_1=r_2=0.15$, $v_1=0.8$, 
$y_1=0.8$, and $s_1\in\{0.05,0.1\}$. 
The requested least upper bound for $u_1<u_2$ or $x_1<x_2$ is
\mbox{the maximum value over $[u_1,u_2]\times[x_1,x_2]$}.

\begin{figure}
\begin{center}
\begin{picture}(0,0)%
\special{psfile=fig05.pstex}%
\end{picture}%
\setlength{\unitlength}{0.012500in}%
\begin{picture}(380,600)(5,235)
\end{picture}
\end{center}
\caption{\label{diss13}Least Upper Bound $z_2$ in the Chaining Example}
\end{figure}

We now transform this nonlinear program into an equivalent linear program
(by replacing $1$, $u$, $ux$, and $uxr$ by the new variables $x_{\sf M}$, $x_{\sf N}$, $x_{\sf O}$, and $x_{\sf P}$, respectively). 
More precisely, the maximum of $z$ subject to $u\in[u_1,u_2]$, $x\in[x_1,x_2]$, $r\in[r_1,r_2]$, 
and the nonlinear inequalities in 
(\ref{BKKK9-1}) to (\ref{BKKK9-5}) coincides with the maximum 
of z subject to the following system of linear inequalities over $z$ and $x_B\ge 0$ ($B\in{\cal B}$):
\begin{displaymath}\phantom{\Box}\baq{rcrcrcrcr}  
z \!\!&\le&\!\! x_{\sf M}          \!\!\!& &\!\!\!                                         \!\!\!& &\!\!\!                                   \!\!\!& &\!\!\!  \\[0.3ex]
z \!\!&\le&\!\! x_{\sf M}          \!\!\!&+&\!\!\! \frac{1-v_1}{v_1}\cdot x_{\sf N}  \!\!\!&-&\!\!\!\frac{y_1}{v_1y_1}\cdot x_{\sf O}             \!\!\!&+&\!\!\!\frac{s_1}{v_1y_1s_1}\cdot x_{\sf P}\\[0.3ex]
z \!\!&\le&\!\! x_{\sf M}          \!\!\!&-&\!\!\!   \frac{v_1}{v_1}\cdot x_{\sf N}   \!\!\!&+&\!\!\!\frac{y_1}{v_1y_1}\cdot x_{\sf O}       \!\!\!&+&\!\!\!\frac{1-s_1}{v_1y_1s_1}\cdot x_{\sf P}\\[0.3ex]
z \!\!&\le&\!\!            \!\!\!& &\!\!\!          \frac{v_1}{v_1}\cdot  x_{\sf N}  \!\!\!&+&\!\!\!\frac{1-y_1}{v_1y_1}\cdot x_{\sf O}\!\!\!&+&\!\!\!\frac{1-s_1}{v_1y_1s_1}\cdot x_{\sf P}\\[0.3ex]
z \!\!&\le&\!\!            \!\!\!& &\!\!\!                                         \!\!\!& &\!\!\!                                   \!\!\!& &\!\!\! \frac{1}{v_1y_1s_1}\cdot x_{\sf P}\\
\eaq\ \ \ \ 
\baq{rcccl}
          1 \!\!&\le&\!\!  x_{\sf M} \!\!&\le&\!\! 1 \\[0.3ex]
u_1\cdot x_{\sf M} \!\!&\le&\!\! x_{\sf N} \!\!&\le&\!\! u_2\cdot x_{\sf M}\\[0.3ex]
x_1\cdot  x_{\sf N} \!\!&\le&\!\! x_{\sf O} \!\!&\le&\!\! x_2\cdot x_{\sf N}\\[0.3ex] 
r_1\cdot    x_{\sf O} \!\!&\le&\!\! x_{\sf P} \!\!&\le&\!\! r_2\cdot x_{\sf O}\\[0.3ex]
\eaq\!\!\end{displaymath} 
More generally, tight upper answers to prem\-ise-re\-strict\-ed com\-plete queries
to conditional constraint trees can be computed by solving similar nonlinear programs, 
which can similarly be transformed into linear programs. 

For example, let us consider the premise-restricted complete query 
$\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$ to the conditional constraint tree 
in Fig.~\ref{diss53++}, right side.
The requested least upper bound is the maximum of $x$ subject to the system of linear inequalities 
in Fig.~\ref{diss13-13}
(we actually generated 72 linear inequalities of which 31 were trivially subsumed by others).
Note that the nine variables $x_{\sf M}$ to $x_{\sf U}$ correspond
to the nine nodes ${\sf M}$ to ${\sf U}$.
\begin{figure}[ht]\vspace*{-2.5ex}
\begin{displaymath}\baq{rcl}   
x \!\!&\le&\!\! x_{\sf M}\\[0.3ex]
x \!\!&\le&\!\! \frac{25}{18} x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\! \frac{25}{2}  x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\! \frac{25}{18} x_{\sf S}\\[0.3ex]
x \!\!&\le&\!\! \frac{25}{18} x_{\sf T}\\[0.3ex]
x \!\!&\le&\!\! \frac{25}{18} x_{\sf U}\\[0.3ex]
x \!\!&\le&\!\!  x_{\sf N} + \frac{1}{9} x_{\sf P}\\[0.3ex]
x \!\!&\le&\!\!  x_{\sf N} + \frac{1}{9} x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\!  x_{\sf N} + \frac{1}{9} x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{4} x_{\sf O} + \frac{5}{36} x_{\sf P}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{4} x_{\sf O} + \frac{5}{36} x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{4} x_{\sf O} + \frac{45}{4} x_{\sf R}\\
\eaq\  \  \  \
\baq{rcl}   
x \!\!&\le&\!\!  \frac{5}{4} x_{\sf P} + \frac{5}{36} x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{36} x_{\sf P} + \frac{5}{4} x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{36} x_{\sf P} + \frac{5}{4} x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\!  \frac{5}{36} x_{\sf Q} + \frac{5}{4} x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} -             x_{\sf N} + \frac{5}{4} x_{\sf O} + \frac{5}{36}  x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf O} + \frac{5}{4}   x_{\sf P}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf O} + \frac{5}{4}   x_{\sf Q}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf O} + \frac{5}{4}   x_{\sf R}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf P} + \frac{25}{18} x_{\sf S}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf P} + \frac{25}{18} x_{\sf T}\\[0.3ex]
x \!\!&\le&\!\! x_{\sf M} + \frac{1}{4} x_{\sf N} - \frac{5}{4} x_{\sf P} + \frac{25}{18} x_{\sf U}\\[0.3ex]
\eaq\  \  \  \
\baq{rcccl}
          1 \!\!&\le&\!\!  x_{\sf M} \!\!&\le&\!\! 1 \\[0.3ex]
\frac{3}{10} x_{\sf M} \!\!&\le&\!\! x_{\sf N} \!\!&\le&\!\! \frac{2}{5} x_{\sf M}\\ [0.3ex]
\frac{1}{2} x_{\sf N} \!\!&\le&\!\! x_{\sf O} \!\!&\le&\!\! \frac{3}{5} x_{\sf N}\\ [0.3ex]
\frac{9}{10}x_{\sf O} \!\!&\le&\!\! x_{\sf R} \!\!&\le&\!\! x_{\sf O} \\[0.3ex]
\frac{9}{10} x_{\sf O} \!\!&\le&\!\! x_{\sf Q} \!\!&\le&\!\! x_{\sf O}\\ [0.3ex]
\frac{4}{5} x_{\sf O} \!\!&\le&\!\! x_{\sf P} \!\!&\le&\!\! \frac{9}{10} x_{\sf O} \\[0.3ex]
\frac{4}{5} x_{\sf P} \!\!&\le&\!\! x_{\sf S} \!\!&\le&\!\! \frac{9}{10} x_{\sf P} \\[0.3ex]
\frac{4}{5} x_{\sf P} \!\!&\le&\!\! x_{\sf T} \!\!&\le&\!\! \frac{9}{10} x_{\sf P} \\[0.3ex]
\frac{4}{5} x_{\sf P} \!\!&\le&\!\! x_{\sf U} \!\!&\le&\!\! \frac{9}{10} x_{\sf P}\\ 
\eaq\end{displaymath}\vspace*{-2ex}
\caption{\label{diss13-13}Generated Linear Inequalities in the Chaining Example}\vspace*{0.5ex}
\end{figure}

Thus, in this example, the tight upper answer is computed by solving
a linear program that has 10 variables and 72 linear inequalities.
Note that computing the tight upper answer by 
the classical linear programming approach would result in solving
a linear program that has $2^9=512$ variables and $4\cdot9-2=34$ linear inequalities (see Section~\ref{LP}).

Let us now focus on the technical details.
We subsequently generalize the function $H^{\alpha}_1$ of Section~\ref{EXCT}
in a straightforward way to compute greatest lower bounds 
in conditional constraint trees. Moreover, we present a linear 
program for computing the requested least 
upper bound in conditional constraint trees.

Let ${\it Pr}_1({\it C}|B)$ denote $u_1$ for all $\urule{B}{u_1,u_2}{C}\in {\it KB}$. 
In the sequel, let $B$ be a node and let $C=B^{\uparrow}$.
Again, the cases $C=B$, $C=B_1$ with a node $B_1\neq B$, 
and $C={\it B_1 B_2}\ldots B_k$ with $k>1$ nodes $B_1,B_2,\ldots$$,B_k$ refer to 
{\sc Leaf}, {\sc Chaining}, and {\sc Fusion}, respectively.

We define the generalized function  ${\it H}^{\alpha}_1$ for computing
greatest lower bounds in conditional constraint trees: 
let ${\it H}^{\alpha}_1(B,C)=\alpha_1$ (note that $\alpha_1$
will coincide with the greatest lower bound of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}({\it B})$ 
subject to ${\it Pr}\models{\it KB}$ and ${\it Pr}(B)>0$),
where $\alpha_1$ in {\sc Leaf} ($C=B$), {\sc Chaining} 
($C=B_1$), and {\sc Fusion} ($C={\it B_1 B_2}\ldots B_k$ with $k>1$) \mbox{is given by}:

\bigskip
\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\alpha_1 & = & 1\\
\eaq$

\bigskip
\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\alpha_1 & = & \max(0,{\it Pr}_1({\it C}|B)\cdot(1+\frac{{\it H}^{\alpha}_1(C,\,C^{\uparrow})-1}{{\it Pr}_1({\it B}\mid C)})) \\
\eaq$

\bigskip
\vbox{\noindent {\sc Fusion}:

\medskip
$\baq{lll}
\alpha_1 & = & \max(0,1-k+\sum\limits_{i=1}^{k}{\it H}^{\alpha}_1(B,B_i))\\
\eaq$}

\bigskip
${\it H}^{\alpha}_1$ is sound and globally complete with respect to $B$ and $C$ iff ${\it H}^{\alpha}_1(B,C)=\alpha_1$ is the greatest lower bound of 
${\it Pr}({\it BL(C)})\,/\,{\it Pr}(B)$ subject to ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
Thus, the next theorem shows soundness and global completeness of ${\it H}^{\alpha}_1$.
\bso\label{LEM1}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) For all probabilistic interpretations ${\it Pr}\in {\it Mo}(B,C)$, it holds $\alpha_1\cdot{\it Pr}(B) \le {\it Pr}(BL(C))$.

\medskip
\noindent b) There exists a probabilistic interpretation 
${\it Pr}\in{\it Mo}(B,C)$ with ${\it Pr}(B)>0$,
$\alpha_1\cdot{\it Pr}(B)={\it Pr}({\it BL(C)})$, 
and $\Pr(\ol{B}L(C))=0$ iff $L(C)$$\,\Rightarrow$$\,B$.
\eso
{\bf Proof.} The claims follow from Theorem~\ref{satzBLB2}. $\Box$

\medskip
Next, we focus on the requested least upper bound, which is computed by
solving a linear program as described in the two examples.

We start by defining the functions $I^{\alpha}$, $I^{\beta}$, and $I^{\gamma}$ over the 
variables $x_B$ ($B\in {\cal B}$). 
Let $I^{\alpha}(B,C)=\alpha_2$, $I^{\beta}(B,C)=\beta_2$, and 
$I^{\gamma}(B,C)=\gamma_2$, where $\alpha_2$, $\beta_2$, and $\gamma_2$ 
in {\sc Leaf} ($C=B$), {\sc Chaining} 
($C=B_1$), and {\sc Fusion} ($C={\it B_1 B_2}\ldots B_k$ with $k>1$) are given as follows:

\bigskip
\vbox{\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\alpha_2 & = & x_B\\
\beta_2 & = & 0\\
\gamma_2 & = & x_B\\
\eaq$}

\bigskip
\vbox{\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\alpha_2& = &\min(x_B,\frac{I^{\gamma}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)},\,x_C
+\frac{I^{\beta}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)},\,
x_B-x_C+\frac{I^{\alpha}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)})\\[1.5ex]
\beta_2& = &\min(\frac{1-{\it Pr}_1(B|C)}{{\it Pr}_1(B|C)}\cdot x_C+
\frac{I^{\beta}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)},\,
\frac{I^{\gamma}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)})\\[1.5ex]
\gamma_2& = &\frac{I^{\gamma}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)}\\
\eaq$}

\bigskip
\noindent {\sc Fusion}:

\medskip
$\baq{lll}
\alpha_2& = &\min\limits_{i\in[1:k]}I^{\alpha}(B,B_i) \\[1.5ex]
\beta_2& = &\min\limits_{i\in[1:k]}I^{\beta}(B,B_i) \\[1.5ex]
\gamma_2& = &\min(\min\limits_{i\in[1:k]}I^{\gamma}(B,B_i),\,
\min\limits_{i,j\in[1:k],i\neq j}(I^{\alpha}(B,B_i)+I^{\beta}(B,B_j)))\\[0.5ex]
\eaq$

\bigskip
The system of linear inequalities $J(B,C)$ is defined as
the least set of linear inequalities over $x_G\ge 0$ ($G\in {\cal B}(B,C)$)
that contains $1\le x_B \le 1$ and $u_1\cdot x_G \le x_H\le u_2\cdot x_G$ 
for all $\urule{G}{u_1,u_2}{H}\in {\it KB}(B,C)$ with $G\rightarrow H$
(that is, $G$ is the parent of $H$). 

The intuition behind these definitions can now be described as follows.

Each $x_G$ $(G\in{\cal B}(B,C))$ that satisfies $J(B,C)$
corresponds to the exact conditional constraint tree $({\cal B}(B,C),{\it KB}'(B,C))$,
where ${\it KB}'(B,C)$ contains the pair
$\urule{G}{x_H\hspace*{-0.5pt}/\hspace*{-0.5pt}x_G,x_H\hspace*{-0.5pt}/\hspace*{-0.5pt}x_G}{H}$ and $\urule{H}{v_1,v_1}{G}$ 
for each pair $\urule{G}{u_1,u_2}{H},\urule{H}{v_1,v_2}{G}\in{\it KB}(B,C)$
with $G\rightarrow H$.
%
%Given some $x_G$ $(G$$\,\in$$\,{\cal B}(B,C))$ that satisfies $J(B,C)$, 

We will show that the least upper bound of ${\it Pr}(BL(C))/{\it Pr}({\it B})$,
${\it Pr}(\ol{B}L(C))/{\it Pr}({\it B})$, 
and ${\it Pr}(L(C))/{\it Pr}({\it B})$ 
subject to ${\it Pr}\models{\it KB}'(B,C)$ and ${\it Pr}(B)>0$
is given by $I^{\alpha}(B,C)$, $I^{\beta}(B,C)$, and $I^{\gamma}(B,C)$, respectively. 
It will then follow that the least upper bound of
${\it Pr}(BL(C))/{\it Pr}({\it B})$,
${\it Pr}(\ol{B}L(C))/{\it Pr}({\it B})$, 
and ${\it Pr}(L(C))/{\it Pr}({\it B})$ 
subject to ${\it Pr}\models{\it KB}(B,C)$ and ${\it Pr}(B)>0$
is given by the maximum of $I^{\alpha}(B,C)$, $I^{\beta}(B,C)$, and 
$I^{\gamma}(B,C)$, respectively, subject 
to all $x_G$ $(G\in{\cal B}(B,C))$ satisfying $J(B,C)$. 

That is, we implicitly performed the variable transformation described in the two examples.
This transformation is indeed correct for conditional constraint trees:

\vbox{\ble \label{567890}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) If $x_G$ $(G\in{\cal B}(B,C))$ satisfies $J(B,C)$, then for all 
con\-di\-tion\-al constraints $\urule{G}{u_1,u_2}{H}\in{\it KB}(B,C)$ 
such that $G\rightarrow H$, there exists
$u_H\in[u_1,u_2]$ with $x_H= u_H \cdot x_G$\,.

\medskip
\noindent b) Let $u_H\in[u_1,u_2]$ for all $\urule{G}{u_1,u_2}{H}\in {\it KB}(B,C)$ 
such that $G\rightarrow H$. There exists $x_G$ $(G\in{\cal B}(B,C))$ with $J(B,C)$ and 
$x_H= u_H \cdot x_G $ for all nodes $H$ with parent $G$.
\ele
{\bf Proof.} a) For all nodes $H$ with parent $G$, let $u_H$ be defined by 
$u_H=x_H\,/\,x_G$.

\medskip
\noindent b) Let $x_B=1$, and for all nodes $H$ with parent $G$, let $x_H$ be defined by
$x_H=u_H\cdot x_G$. $\Box$}                       

\medskip
We are now ready to formulate an optimization problem 
for computing the requested least upper bound.
\bso \label{HALLO1}%\hspace*{10ex}\phantom{.}
Let ${\it X}_2$ be the maximum of $x$ subject to $x\le I^{\alpha}(E,E^{\uparrow})$ and $J(E,E^{\uparrow})$.

\medskip
\noindent a) ${\it Pr}(EL(E^{\uparrow})) \le {\it X}_2\cdot{\it Pr}(E)$ for all ${\it Pr}\in {\it Mo}(E,E^{\uparrow})$.

\medskip
\noindent b) There exists ${\it Pr}\in{\it Mo}(E,E^{\uparrow})$ with ${\it Pr}(E)>0$ and ${\it Pr}({\it EL(E^{\uparrow})})={\it X}_2\cdot{\it Pr}(E)$. 
\eso
{\bf Proof.} Let ${\it Pr}(B|C)=v_1$ for all $\urule{C}{v_1,v_2}{B}\in {\it KB}$ 
such that $B\rightarrow C$.
By Theorem~\ref{GRAPHU}, the requested least upper bound is 
the maximum of $x$ subject to $x\le {\it H}^{\alpha}_2(E,E^{\uparrow})$ and ${\it Pr}(C|B)=u_C\in[u_1,u_2]$
for all $\urule{B}{u_1,u_2}{C}\in {\it KB}$ such that $B\rightarrow C$. 
By Lemma~\ref{567890}, we can equivalently maximize $x$
subject to $x\le I^{\alpha}(E,E^{\uparrow})$ and $J(E,E^{\uparrow})$. $\Box$

\medskip
We now wonder how to solve the generated optimization problem, since $I^{\alpha}(E,E^{\uparrow})$
may still contain min-operations that cannot be tackled by linear programming. Moreover, given a method
for solving this optimization problem, we are also interested in a rough idea on the overall time complexity
of computing the requested least upper bound this way. Finally, we are interested in possible improvements to
increase efficiency. These topics are discussed in the rest of this section.

If $I^{\alpha}(E,E^{\uparrow})$ does not contain any min-operations at all,
then the generated optimization problem is already a linear program. Otherwise, 
it can easily be transformed into a linear program.
In a first transformation step, all inner min-operations are eliminated.
This can easily be done due to the well-structuredness of $I^{\alpha}(E,E^{\uparrow})$.
In a second step, the only remaining outer min-operation is eliminated by introducing exactly one linear inequality
for each contained operand. In these linear inequalities, the operands of the outer min-operation
are upper bounds of $x$.

To get a rough idea on the time complexity of computing the requested least upper bound this way,
we must analyze the size of the generated linear programs.
It is given by the number of variables, the number of linear inequalities in $J(E,E^{\uparrow})$,
and the number of linear inequalities extracted from $x\le I^{\alpha}(E,E^{\uparrow})$.
The latter is quite worrying, since
$I^{\gamma}(B,C)$ in {\sc Fusion} seems to produce many min-operands. Moreover, 
$I^{\gamma}(B,C)$ in {\sc Fusion} contains $I^{\alpha}(B,B_i)$, and 
$I^{\alpha}(B,C)$ in {\sc Chaining} contains $I^{\gamma}(C,C^{\uparrow})$.
So, due to this crossed dependency, the overall number of generated linear inequalities 
is likely to \mbox{`explode' for trees that branch very often}. 

To avoid these problems, we introduce the auxiliary functions $J^{\alpha}$, 
$J^{\beta}$, and $J^{\gamma}$ over the variables $x_B$ \mbox{($B\in {\cal B}$)}.
Let $J^{\alpha}(B,C)=\alpha_2'$, $J^{\beta}(B,C)=\beta_2'$, and 
$J^{\gamma}(B,C)=\gamma_2'$, where $\alpha_2'$, $\beta_2'$, and $\gamma_2'$ 
in {\sc Leaf} ($C=B$), {\sc Chaining} ($C=B_1$), and {\sc Fusion} \mbox{($C={\it B_1 B_2}\ldots B_k$ with $k>1$)} are given as follows:

\bigskip
\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\alpha_2' & = & x_B\\
\beta_2' & = & 0\\
\gamma_2' & = & x_B\\
\eaq$

\bigskip
\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\alpha_2'& = & \min(x_B,\,x_C+\frac{J^{\beta}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)},\,x_B-x_C+\frac{J^{\alpha}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)})\\[1.5ex]
\beta_2'& = &\frac{1-{\it Pr}_1(B|C)}{{\it Pr}_1(B|C)}\cdot x_C+
\frac{J^{\beta}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)}\\[1.5ex]
\gamma_2'& = &\frac{J^{\gamma}(C,\,C^{\uparrow})}{{\it Pr}_1(B|C)}\\
\eaq$

\bigskip
\vbox{\noindent {\sc Fusion}: 

\medskip
$\baq{lll}
\alpha_2'& = &\min\limits_{i\in[1:k]}J^{\alpha}(B,B_i) \\[1.5ex]
\beta_2'& = &\min\limits_{i\in[1:k]}J^{\beta}(B,B_i) \\[1.5ex]
\gamma_2'& = &\min(\min\limits_{i\in[1:k]}J^{\gamma}(B,B_i),\,
\min\limits_{i,j\in[1:k],i\neq j}(J^{\alpha}(B,B_i)+J^{\beta}(B,B_j)))\\
\eaq$}

\bigskip
Note that $\alpha_2'$ in {\sc Chaining} can be separated into
the cases $C^{\uparrow}=C$ and $C^{\uparrow}\neq C$. Since simply $\alpha_2'=x_C$
for $C^{\uparrow}=C$, we reduce the number of generated linear inequalities this way.

The next lemma shows that the functions $I^{\alpha}$, 
$I^{\beta}$, and $I^{\gamma}$ can be 
expressed in terms of the auxiliary functions $J^{\alpha}$, 
$J^{\beta}$, and $J^{\gamma}$.
\ble\label{LEMIM}
For all $x_B$ $(B\in{\cal B})$ that satisfy $J(E,E^{\uparrow})$:
\begin{center}
$\alpha_2=\min(\alpha_2',\gamma_2')$, $\beta_2=\min(\beta_2',\gamma_2')$,
and $\gamma_2=\gamma_2'\,.$
\end{center}
\ele
{\bf Proof sketch.} The claim can be proved by induction on the recursive definition of the functions $I^{\alpha}$, 
$I^{\beta}$, and $I^{\gamma}$. $\Box$

\medskip
Briefly, by Theorem~\ref{LEM1}, Theorem~\ref{HALLO1}, 
and Lemma~\ref{LEMIM}, 
the tight answer to the premise-restricted complete query $\exists\urule{E}{x_1,x_2}{F}$ is  
given by $\{x_1/{\it H}^{\alpha}_1(E,E^{\uparrow}),\,x_2/{\it X}_2\}$, where ${\it X}_2$ is the maximum 
of $x$ subject to
$x\le J^{\alpha}(E,E^{\uparrow})$, $x\le J^{\gamma}(E,E^{\uparrow})$, and $J(E,E^{\uparrow})$. 

In our example, we get $\{x_1/0.00,\,x_2/0.27\}$ as the tight answer to 
the premise-restricted complete query $\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$
to the conditional constraint tree in Fig.~\ref{diss53++}, right side.

The time complexity of computing
the requested greatest lower bound and especially the requested least upper bound this way 
is analyzed in Section~\ref{SECTC}. 

\subsection{Strongly Conclusion-Restricted Complete Queries}\label{SCRCQ}
We now focus on computing the tight answer to strongly conclusion-restricted 
complete queries to general conditional constraint trees. In the sequel, let
$({\cal B},{\it KB})$ be a conditional constraint tree and 
let $\exists\urule{E}{x_1,x_2}{F}$ be a strongly conclusion-restricted complete query. 

The tight upper answer to $\exists\urule{E}{x_1,x_2}{F}$ is always 
given by $\{x_2/1\}$. To compute the tight lower answer  to $\exists\urule{E}{x_1,x_2}{F}$, 
we first compute the tight lower answer $\{y_1/u_1\}$ to the premise-restricted 
complete query $\exists\urule{F}{y_1,y_2}{E}$. 
We then distinguish the following cases:

If $u_1>0$, then the tight lower answer to $\exists\urule{E}{x_1,x_2}{F}$ is computed locally by 
a function $H^{\delta}_1$ (like the tight lower answer to premise-restricted complete queries 
in Section~\ref{EXXX}). \mbox{If $u_1=0$} and $E\Rightarrow F$, then the tight lower answer  to 
$\exists\urule{E}{x_1,x_2}{F}$ is given by $\{x_1/1\}$. Otherwise, the tight lower answer  to 
$\exists\urule{E}{x_1,x_2}{F}$ is given by $\{x_1/0\}$.

We now focus on the technical details. Let $({\cal B},\rightarrow)$ be the directed graph 
that belongs to the premise-restricted complete query $\exists\urule{F}{y_1,y_2}{E}$ (see Section~\ref{EXCT}).
Let ${\it Pr}_1(B|C)$ denote $v_1$ for all $\urule{C}{v_1,v_2}{B}\in {\it KB}$.
In the sequel, let $B$ be a node and let $C=B^{\uparrow}$.
Again, the cases $C=B$, $C=B_1$ with a node $B_1\neq B$, 
and $C={\it B_1 B_2}\ldots B_k$ with $k>1$ nodes $B_1,B_2,\ldots$$,B_k$ refer to 
{\sc Leaf}, {\sc Chaining}, and \mbox{{\sc Fusion}, respectively.}

We define the function ${\it H}^{\delta}_1$ for computing greatest 
lower bounds in the case ${\it H}^{\alpha}_1(B,C)>0$ as follows. 
Let ${\it H}^{\delta}_1(B,C)=\delta_1$
(note that $\delta_1$ will coincide 
with the greatest lower bound of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}(L(C))$ 
subject to ${\it Pr}\models{\it KB}$ and ${\it Pr}(L(C))>0$), where $\delta_1$ in
{\sc Leaf} ($C=B$), {\sc Chaining} ($C=B_1$), and {\sc Fusion} ($C={\it B_1 B_2}\ldots B_k$ with $k>1$) 
is given as follows (note that ${\it H}^{\alpha}_1(C,C^{\uparrow})$ and 
${\it H}^{\alpha}_1(B,B_i)$ are defined like in Section~\ref{EXXX}):

\bigskip
\vbox{\noindent {\sc Leaf}:

\medskip
$\baq{lll}
\delta_1 & = & 1\\
\eaq$

\bigskip
\noindent {\sc Chaining}:

\medskip
$\baq{lll}
\delta_1 & = & {\it H}^{\delta}_1(C,C^{\uparrow})\cdot(1+\frac{{\it Pr}_1(B|C)-1}{{\it H}^{\alpha}_1(C,C^{\uparrow})}) \\
\eaq$}

\bigskip
\noindent {\sc Fusion}:

\medskip
$\baq{lll}
\delta_1 & = & \left(1+\frac{\min\limits_{i\in[1:k]}
{\it H}^{\alpha}_1(B,B_i)\cdot(1/{\it H}^{\delta}_1(B,B_i) - 1)}{1-k+\sum\limits_{i=1}^{k}{\it H}^{\alpha}_1(B,B_i)}\right)^{-1}\\
\eaq$

\bigskip 
By induction on the definition of ${\it H}^{\delta}_1$, it is easy to see that 
${\it H}^{\alpha}_1(B,C)>0$ entails that $\delta_1$ is defined and that $\delta_1>0$
(note that ${\it H}^{\alpha}_1(B,C)=\alpha_1$ 
in {\sc Leaf}, {\sc Chaining}, and {\sc Fusion} is defined like in Section~\ref{EXXX}). In this case, 
${\it H}^{\delta}_1$ is sound and globally complete with respect to $B$ and $C$ 
iff \mbox{${\it H}^{\delta}_1(B,C)=\delta_1$}
is the greatest lower bound of ${\it Pr}({\it BL(C)})\,/\,{\it Pr}(L(C))$ subject to ${\it Pr}\in{\it Mo}(B,C)$ 
and \mbox{${\it Pr}(L(C))>0$}.
Thus, the next theorem shows soundness and global completeness of ${\it H}^{\delta}_1$.
It also shows that, for $C={\it B_1 B_2}\ldots B_k$ with $k>1$, the least upper bound of 
${\it Pr}({\it BL(C)})\,/\,{\it Pr}(L(C))$ subject to ${\it Pr}\in{\it Mo}(B,C)$ and 
${\it Pr}(L(C))>0$ is \mbox{given by 1}.

\vbox{\bso\label{NEUT}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) If $\alpha_1>0$, then for all ${\it Pr}\in {\it Mo}(B,C)$, it holds $\delta_1\cdot{\it Pr}(L(C)) \le {\it Pr}(BL(C))$.

\medskip
\noindent b) If $\alpha_1>0$, then there is a probabilistic interpretation ${\it Pr}\in{\it Mo}(B,C)$ with ${\it Pr}(B)>0$, ${\it Pr}(L(C))>0$,
$\delta_1\cdot{\it Pr}(L(C))={\it Pr}(BL(C))$, and $\alpha_1\cdot{\it Pr}(B)={\it Pr}({\it BL(C)})$. 

\medskip
\noindent c) If $\alpha_1>0$ and $C={\it B_1 B_2}\ldots B_k$ with $k>1$, then there is some ${\it Pr}\in{\it Mo}(B,C)$ with ${\it Pr}(B)>0$, ${\it Pr}(L(C))>0$,
$1\cdot{\it Pr}(L(C))={\it Pr}(BL(C))$, and $\alpha_1\cdot{\it Pr}(B)={\it Pr}({\it BL(C)})$. 

\medskip
\noindent d) If $\alpha_1$$\,=$$\,0$ and $C$$\,=$$\,{\it B_1 B_2}\ldots B_k$ with $k$$\,>$$\,1$, then for each $\varepsilon$$\,>$$\,0$ there is 
some ${\it Pr}$$\,\in$$\,{\it Mo}(B,C)$ with ${\it Pr}(B)>0$, ${\it Pr}(L(C))>0$,
$1\cdot{\it Pr}(L(C))={\it Pr}(BL(C))$, and $\varepsilon\cdot{\it Pr}(B)\ge {\it Pr}({\it BL(C)})$.
\eso
{\bf Proof.} The proof is given in full detail in Appendix C. $\Box$}

\medskip 
We are now ready to give the following characterization of tight answers to
strongly conclusion-restricted complete queries to
conditional constraint trees.
%
\bso\label{Theorem48}
Let $({\cal B},{\it KB})$ be a conditional constraint tree 
and let $\exists\urule{E}{x_1,x_2}{F}$ be a 
strongly conclusion-restricted complete query. 
Let the tight lower answer to the prem\-ise-re\-strict\-ed complete query 
$\exists\urule{F}{y_1,y_2}{E}$ be given by $\{y_1/u_1\}$.
\be
\item[$(1)$] If $u_1>0$, then the tight answer to $\exists\urule{E}{x_1,x_2}{F}$ is given 
             by $\{x_1/{\it H}^{\delta}_1(F,F^{\uparrow}),\,x_2/1\}$.
\item[$(2)$] If $u_1=0$ and $E\Rightarrow F$, 
             then the tight answer to $\exists\urule{E}{x_1,x_2}{F}$ is given by $\{x_1/1,\,x_2/1\}$.  
\item[$(3)$] Otherwise, the tight answer to $\exists\urule{E}{x_1,x_2}{F}$ is given by $\{x_1/0,\,x_2/1\}$.
\ee
\eso
{\bf Proof.} The proof is given in full detail in Appendix C. $\Box$

\subsection{Complete Queries}\label{QUERYY}

We now show that the problem of computing tight answers to complete queries
can be reduced to the problems of computing tight answers to premise-restricted complete queries 
and of computing tight answers to strongly conclusion-restricted complete queries.

In detail, a complete query is prem\-ise-re\-strict\-ed, it is strongly con\-clu\-sion-re\-strict\-ed, 
or it can be reduced to premise-restricted complete queries and to strongly conclusion-restricted complete queries.
For example, given the complete query $\exists\urule{{\sf MQR}}{x_1,x_2}{{\sf STU}}$
to the conditional constraint tree in Fig.~\ref{diss53++}, right side, we first compute
the tight answer $\{y_1/u_1,\,y_2/u_2\}$ to the prem\-ise-re\-strict\-ed complete 
query $\exists\urule{{\sf O}}{y_1,y_2}{{\sf MQR}}$ (directed to the corresponding subtree) and
the tight answer $\{z_1/v_1,\,z_2/v_2\}$ to the strongly con\-clu\-sion-re\-strict\-ed complete 
query $\exists\urule{{\sf MQR}}{z_1,z_2}{{\sf O}}$ (directed to the corresponding subtree). 
We then generate a new conditional constraint tree
by replacing the subtree over the nodes {\sf M}, {\sf N}, {\sf O}, {\sf Q}, and {\sf R} 
by the pair of conditional constraints 
$\urule{{\sf O}}{u_1,u_2}{{\sf B}}$ and
$\urule{{\sf B}}{v_1,v_2}{{\sf O}}$ 
over the nodes ${\sf B}$ and ${\sf O}$
(note that ${\sf B}$ represents ${\sf MQR}$). 
Finally, we compute the tight answer 
to the premise-restricted complete query 
$\exists\urule{{\sf B}}{x_1,x_2}{{\sf STU}}$ 
to the new conditional constraint tree.

Note that this reduction can always be done, since for each query $\exists\urule{E}{x_1,x_2}{F}$,
all paths from a basic event in $E$ to a basic event in $F$ have at least one basic 
event in common.

\bso\label{ZZZ}\label{Theorem49}
Let $({\cal B},{\it KB})$ be a conditional constraint tree 
and let $\exists\urule{E}{x_1,x_2}{F}$ be a complete query that is not premise-restricted
and not strongly conclusion-restricted. 

\medskip
\noindent a) There exists a basic event $G\in{\cal B}$ and two conditional constraint trees
$({\cal B}_1,{\it KB}_1)$ and $({\cal B}_2,{\it KB}_2)$ 
such that ${\cal B}_1\cap{\cal B}_2=\{G\}$,
${\cal B}_1\cup {\cal B}_2={\cal B}$,
and $\exists\urule{E}{z_1,z_2}{G}$ is a strongly con\-clu\-sion-re\-strict\-ed complete query to
$({\cal B}_1,{\it KB}_1)$.

\medskip
\noindent b) Let the tight answer to the prem\-ise-re\-strict\-ed complete query 
$\exists\urule{G}{y_1,y_2}{E}$ to $({\cal B}_1,{\it KB}_1)$ be given by $\{y_1/u_1,\,y_2/u_2\}$
and let the tight answer to the 
strongly con\-clu\-sion-re\-strict\-ed complete query 
$\exists\urule{E}{z_1,z_2}{G}$ to $({\cal B}_1,{\it KB}_1)$ be given by $\{z_1/v_1,\,z_2/v_2\}$.
\be
\item[$(1)$] If $u_1>0$, then also $v_1>0$ and the tight answer to 
the complete query $\exists\urule{E}{x_1,x_2}{F}$ to $({\cal B},{\it KB})$ 
coincides with the tight answer to the prem\-ise-re\-strict\-ed complete query $\exists\urule{B}{x_1,x_2}{F}$ to 
$({\cal B}_2\cup\{B\},{\it KB}_2\cup\{\urule{G}{u_1,u_2}{B},\urule{B}{v_1,v_2}{G}\})$, where 
$B$ is a new basic event with $B\not\in{\cal B}_2$. 
In particular, for exact conditional constraint trees $({\cal B},{\it KB})$, the tight answer to 
the complete query $\exists\urule{E}{x_1,x_2}{F}$ is given by:
\begin{displaymath}\baq{l}
\{x_1/\max(0,v_1-\frac{v_1}{u_1}+\frac{v_1 s_1}{u_1}),\ 
x_2/\min(1,1-v_1+\frac{v_1s_2}{u_1},\frac{t_2}{t_2-s_2+u_1})\}\,,\\\eaq
\end{displaymath}
where $s_1={\it H}^{\alpha}_1(G,G^{\uparrow})$, $s_2={\it H}^{\alpha}_2(G,G^{\uparrow})$, and
$t_2={\it H}^{\gamma}_2(G,G^{\uparrow})$ (note that ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, 
and ${\it H}^{\gamma}_2$ are defined like 
in Section~\ref{EXCT}).
\item[$(2)$] If $u_1\!=\!0$, $v_1\!=\!1$, and $G$$\,\Rightarrow$$\,F$,
then the tight answer to the complete query $\exists\urule{E}{x_1,x_2}{F}$ to $({\cal B},{\it KB})$ 
is given by $\{x_1/1,\,x_2/1\}$. 
\item[$(3)$] Otherwise, the tight answer to the  complete query $\exists\urule{E}{x_1,x_2}{F}$ to $({\cal B},{\it KB})$ 
is given by $\{x_1/0,\,x_2/1\}$. 
\ee
\eso
{\bf Proof.} The proof is given in full detail in Appendix D. $\Box$

%\medskip
%Hence, we can restrict the rest of this work to computing tight answers to 
%premise-restricted complete queries and to strongly conclusion-restricted complete queries.

 
\subsection{Queries}\label{QUERY}
%
The problem of computing tight answers to queries 
can be reduced to the more specialized problem of calculating 
tight answers to complete queries.

More precisely, given a query 
$\exists\urule{E}{x_1,x_2}{F}$ to a conditional constraint tree 
$({\cal B},{\it KB})$, \mbox{a complete query $\exists\urule{E'}{x_1,x_2}{F'}$} 
to a conditional constraint tree $({\cal B}',{\it KB}')$
is generated by: 
\begin{itemize}
\item[1.] While $({\cal B},{\it KB})$ contains a leaf $B$ that is not contained in ${\it EF}$: remove
$B$ from ${\cal B}$ and remove the corresponding pair $\urule{B}{u_1,u_2}{C},\urule{C}{v_1,v_2}{B}\in{\it KB}$ 
from ${\it KB}$.
\item[2.] While ${\it EF}$ contains a basic event $B$ that is not a leaf in $({\cal B},{\it KB})$: 
increase ${\cal B}$ by a new basic event $B'$, 
increase ${\it KB}$ by the pair $\urule{B}{1,1}{B'}$ and $\urule{B'}{1,1}{B}$, 
and replace each occurrence of $B$ in $\exists\urule{E}{x_1,x_2}{F}$ by the new basic event $B'$.
\end{itemize}

It remains to show that the generated probabilistic deduction problem 
has the same solution as the original probabilistic deduction problem: 
\bso
The tight answer to the query $\exists\urule{E}{x_1,x_2}{F}$ to $({\cal B},{\it KB})$ 
coincides with the tight answer to
the complete query $\exists\urule{E'}{x_1,x_2}{F'}$ to $({\cal B}',{\it KB}')$.
\eso
{\bf Proof.} Let $({\cal B}'',{\it KB}'')$ be the conditional constraint tree that is generated in step 1
and let $\urule{E}{u_1,u_2}{F}$ be a tight logical consequence of ${\it KB}''$. 
We now show that $\urule{E}{u_1,u_2}{F}$ is also a tight logical consequence of ${\it KB}$.
First, $\urule{E}{u_1,u_2}{F}$ is a \mbox{logical consequence of ${\it KB}$}, 
since ${\it KB}''$ is a subset of ${\it KB}$. Moreover, each model ${\it Pr}''$ 
of ${\it KB}''$ (that is defined on all atomic events over ${\cal B}''$) 
can be extended to a model ${\it Pr}$ of ${\it KB}$ (that is defined on all atomic events over ${\cal B}$)
with ${\it Pr}(A)=s\cdot {\it Pr}''(A)$ for 
all atomic events $A$ over ${\cal B}''$ that are different from the conjunction of all negated basic events
in ${\cal B}''$, where $s$ is a real number from $(0,1]$. This model can be
constructed inductively like in the proof of Theorem~\ref{Doll}. Thus, 
for $u\in[u_1,u_2]$, ${\it Pr}''(E)>0$ and $u\cdot {\it Pr}''(E)={\it Pr}''({\it EF})$ entails
${\it Pr}(E)>0$ and $u\cdot {\it Pr}(E)={\it Pr}({\it EF})$.

Finally, $\urule{E}{u_1,u_2}{F}$ is a tight logical consequence of ${\it KB}''$ iff
$\urule{E'}{u_1,u_2}{F'}$ is a tight logical consequence of ${\it KB}'$, 
since we just introduce synonyms for basic events in step 2. $\Box$

%\medskip
%Hence, without loss of generality, we can restrict the subsequent considerations of this
%work to computing tight answers to complete queries. 
 
\subsection{Computational Complexity}\label{SECTC}

\subsubsection{Exact Conditional Constraint Trees}

We now show that for exact conditional constraint trees, 
our technique to compute the tight answer to queries runs in linear
time in the number of nodes of the tree. In the sequel, let 
$({\cal B},{\it KB})$ be an exact conditional constraint tree
and let $n$ denote its number of nodes.

\ble\label{ERT}
The tight answer to a premise-restricted or strongly conclusion-restricted complete query
can be computed in linear time in $n$.
\ele 
{\bf Proof.} For exact conditional constraint trees, 
our approach to compute the tight upper answer to premise-restricted complete queries
by $H^{\alpha}_2$, $H^{\beta}_2$, and $H^{\gamma}_2$ runs in time $O(n)$: 
 
The directed tree can be computed in time $O(n)$.
An initialization of a leaf with a constant number of assignments is performed 
exactly for each leaf of the directed tree, a chaining with a 
constant number of arithmetic operations is performed exactly for each arrow of the directed tree.
Hence, initializing all leaves and performing all chainings runs in time $O(n)$.
A fusion is done for each branching of the directed tree, using linear time in the number 
of branches. Thus, all fusions together run in time $O(n)$. 

Even for general conditional constraint trees, the tight lower answer
to premise-restricted complete queries, and hence also the tight answer to 
strongly conclusion-restricted complete queries, is analogously computed in time $O(n)$. $\Box$

\bso\label{HHH}
The tight answer to a query can be computed in linear time in $n$.
\eso 
{\bf Proof.} We assume that the set of basic events ${\cal B}$ is totally ordered 
and that the basic events in the conjunctive events $E$ and $F$ of the query 
$\exists\urule{E}{x_1,x_2}{F}$ are written in this order. 

First, the query is reduced to a complete query according to Section~\ref{QUERY}.
This reduction can be done in time $O(n)$. Now, if the generated complete query
is premise-restricted or strongly conclusion-restricted, then the claim follows immediately from Lemma~\ref{ERT}. 

Otherwise, the generated complete query is reduced to premise-restricted and 
strongly con\-clu\-sion-re\-strict\-ed complete queries according to 
Section~\ref{QUERYY}. Also this reduction can be done in \mbox{time $O(n)$}, 
since the basic event $G$ in Theorem~\ref{ZZZ} a) is computable in \mbox{time $O(n)$}.
Hence, the claim follows from Theorem~\ref{ZZZ} and Lemma~\ref{ERT}. Note that 
$t_2={\it H}^{\gamma}_2(G,G^{\uparrow})$ in Theorem~\ref{ZZZ} b) (1) 
can also be computed in time $O(n)$. $\Box$

\subsubsection{Conditional Constraint Trees}
For general conditional constraint trees, our technique to compute 
the tight lower answer to queries runs still
in linear time, while our technique to compute 
the tight upper answer to queries runs in polynomial time in the number of nodes of the tree.
In the sequel, let 
$({\cal B},{\it KB})$ be a general conditional constraint tree
and let $n$ denote its number of nodes.

\ble\label{L99}\hspace*{10ex}\phantom{.}

\medskip
\noindent a) The tight lower answer to a premise-restricted complete query
and the tight answer to a strongly conclusion-restricted complete query can be 
computed in linear time in $n$.

\medskip
\noindent b) The tight upper answer to a premise-restricted complete query
can be computed in polynomial time in $n$.
\ele 
{\bf Proof.} a) The claim is already shown in the proof of Lemma~\ref{ERT}.

\medskip
\noindent b) Our linear programming technique to compute
the tight upper answer to premise-restricted complete queries runs
in polynomial time in $n$:

Linear programming runs in polynomial time 
in the size of the linear programs (Papadimitriou \& Steiglitz, 1982;  
Schrijver, 1986), where the size of a linear program
is given by its number of variables and its number of linear inequalities.

We now show that the size of our linear programs in Section~\ref{EXXX} is \mbox{polynomial in $n$}.
The number of variables is $n+1$.  The number of
linear inequalities in $J(E,E^{\uparrow})$ is $2n$. By induction on the recursive definition of $J^{\alpha}$, $J^{\beta}$, 
and $J^{\gamma}$, 
it can be shown that the number of min-operands in $J^{\alpha}(B,C)$, $J^{\beta}(B,C)$, 
and $J^{\gamma}(B,C)$ is limited by
$|{\cal B}(B,C)|^2$, $|{\cal B}(B,C)|$, and $|{\cal B}(B,C)|^4$, \mbox{respectively}. 
Hence, the number of linear inequalities extracted from
$x\le J^{\alpha}(E,E^{\uparrow})$ and $x\le J^{\gamma}(E,E^{\uparrow})$ is limited by
$|{\cal B}(E,E^{\uparrow})|^2+|{\cal B}(E,E^{\uparrow})|^4$ $=$ $n^2+n^4$. 
Thus, the overall number of generated linear \mbox{inequalities $l$} is limited by $l_u=2n+n^2+n^4$.

Finally, note that $l_u$ is a very rough upper bound for $l$, in many conditional constraint trees
(especially in those that branch very rarely), $l$ is much lower than $l_u$.
For example, taking a complete binary tree with $n=127$ nodes, 
we get only $l=19\,964$ compared to $l_u=260\,161\,024$.
In the example of Section~\ref{EXXX} with $n=9$ nodes, 
we get only $l=72$ compared to $l_u=6\,660$.
Another example is a tree that is degenerated to a chain of 
basic events. In this case, we even get $l=5n+1$, that is,
the overall number of generated linear inequalities is linear in $n$. $\Box$

\bso\hspace*{10ex}\phantom{.}

\medskip
\noindent a) The tight lower answer to  a query can be computed in linear time in $n$.

\medskip
\noindent b) The tight upper answer to a query can be computed in polynomial time in $n$.
\eso 
{\bf Proof.} We assume that the set of basic events ${\cal B}$ is totally ordered 
and that the basic events in the conjunctive events $E$ and $F$ of the query 
$\exists\urule{E}{x_1,x_2}{F}$ are written in this order.

Like in the proof of Theorem~\ref{HHH}, 
the query is reduced to a complete query according to Section~\ref{QUERY}.
This reduction can be done in time $O(n)$. Now, if the generated complete query
is premise-restricted or strongly conclusion-restricted, then the claims follow 
\mbox{immediately from Lemma~\ref{L99}}. 

Otherwise, the generated complete query is reduced to premise-restricted and strongly con\-clu\-sion-re\-strict\-ed complete queries according to 
Section~\ref{QUERYY}. Again, this reduction can be done in \mbox{time $O(n)$}, 
since the basic event $G$ in Theorem~\ref{ZZZ} a) is computable in \mbox{time $O(n)$}.
Thus, the claims follow from Theorem~\ref{ZZZ} and Lemma~\ref{L99}. Note that 
in Theorem~\ref{ZZZ}~b)~(1), the tight lower answer to $\exists\urule{B}{x_1,x_2}{F}$ 
can be computed without $u_2$ and $v_2$. $\Box$

\subsection{Comparison with the Classical Linear Programming Approach}\label{LP}

As a comparison, we now briefly describe how probabilistic deduction 
in conditional constraint trees can be done by the classical linear programming 
approach (Paa\ss{}, 1988; van der Gaag, 1991; Amarger et al.\ 1991;
Hansen et al.\ 1995).
In the sequel, let $\exists\urule{E}{x_1,x_2}{F}$ be a query to an exact or general 
conditional constraint tree $({\cal B},{\it KB})$ over $n$ nodes. 

The tight answer to $\exists\urule{E}{x_1,x_2}{F}$ can be computed by solving two linear programs. 
In detail, the requested greatest lower and least upper bound are given by
the optimal values of the following two linear programs with
$x_A\ge 0$ ($A\in{\cal A}_{\cal B}$) and ${\rm opt}\in\{\min,\max\}$:
\begin{equation*}\begin{array}{c}
  \begin{array}{l}{\rm opt}\ \sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it EF}} x_A\ \, \mbox{subject to}\\\end{array}\\[1.5ex]
\begin{array}{lll}
\sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it E}} x_A\!&=\!&1\\[1ex]
\sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it GH}}x_A \!&\ge\!& 
u_1\cdot\sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it G}}x_A\mbox{ for all $\urule{G}{u_1,u_2}{H}\in{\it KB}$}\hspace*{-2ex}\\[1ex]
\sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it GH}}x_A\!&\le \!& 
u_2\cdot\sum_{A\in{\cal A}_{\cal B},\,A\Rightarrow{} {\it G}}x_A\mbox{ for all $\urule{G}{u_1,u_2}{H}\in{\it KB}$}\hspace*{-2ex}\\[1ex]
\end{array}\\
\end{array}\end{equation*}

That is, the tight answer is computed by solving two linear programs 
with $2^{n}$ variables and $4n-2$ linear inequalities.
For example, the tight answer to the premise-restricted complete 
query $\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$
to the conditional constraint trees in Fig.~\ref{diss53++}\, yields two linear programs
with $2^9=512$ variables and $4\cdot9-2=34$ linear inequalities.

%\newpage
Hence, if we now solve these two linear programs by the standard simplex method or 
the standard interior-point technique, then we need immediately exponential time in $n$.
It is still an open question whether column generation techniques can
help to solve the two linear programs in less than exponential time in $n$ in the worst case.

\vspace*{0.4ex}
\section{Comparison with Bayesian Networks}\label{Bayes}
\vspace*{0.3ex}
In this section, we briefly discuss the relationship between 
conditional constraint trees and Bayesian networks (Pearl, 1988). 

A Bayesian network is defined by
a directed acyclic graph $G$ over discrete random variables $X_1,X_2,\ldots$$,X_n$ as nodes
and by a conditional probability distribution ${\it Pr}(X_i|\!\>\boldsymbol{\rm pa}(X_i))$ for each random variable $X_i$
and each instantiation $\boldsymbol{\rm pa}(X_i)$ of its parents ${\rm pa}(X_i)$.
It specifies a unique joint probability distribution ${\it Pr}$ over 
$X_1,X_2,\ldots$$,X_n$ by:
\begin{equation*}
{\it Pr}(\mbox{$X_1,X_2,\ldots$$,X_n$}) =  \prod\limits^n_{i=1}{\it Pr}(X_i|\!\>{\rm pa}(X_i))\,.
\end{equation*}
That is, the joint probability distribution ${\it Pr}$ is uniquely determined by
the conditional distributions ${\it Pr}(X_i|\boldsymbol{\rm pa}(X_i))$ and
certain conditional independencies encoded in $G$.

Hence, Bayesian trees (that is, Bayesian networks that have a directed tree 
as associated directed acyclic graph) with only 
binary random variables seem to be very close 
to exact conditional constraint trees. 
However, exact and general conditional constraint trees 
are associated with an undirected tree that does not encode any independencies$\!\>$!  
For this reason, exact and general conditional constraint trees describe convex sets of
joint probability distributions rather than single joint probability distributions.
 
But, would it be possible to additionally assume certain independencies?
Of course, with each exact or general conditional constraint tree $({\cal B},{\it KB})$, 
we can associate all probabilistic interpretations ${\it Pr}$ that are models of ${\it KB}$
and that have additionally the undirected tree $({\cal B},\leftrightarrow)$ as an I-map (Pearl, 1988). 
That is, we would have independencies without causal directionality like in Markov trees (Pearl, 1988).
However, this idea does not carry us to a single probabilistic interpretation (neither for 
exact conditional constraint trees, nor for general conditional constraint trees), and
it is an interesting topic of future research to investigate
how the computation of tight answers in exact and general conditional constraint 
trees changes under this kind of independencies (which yield tighter bounds, since they 
reduce the number of models of exact and general conditional constraint trees). 

Finally, if we additionally fix the probability of exactly one node, then 
an exact conditional constraint tree under the described independencies 
specifies exactly one probabilistic interpretation (note that, to keep satisfiability, 
the probability of a node must respect certain
upper bounds, which are entailed by
the exact conditional constraint tree).  But, such exact conditional constraint trees
are in fact Bayesian trees with only binary random variables. 

\vspace*{0.4ex}
\section{Summary and Conclusions}\label{SECC}
\vspace*{0.3ex}
We showed that globally complete probabilistic deduction with conditional constraints over 
basic events is NP-hard. We then concentrated on the special case of 
probabilistic deduction in exact and general conditional constraint trees. 
We presented very efficient techniques for globally complete probabilistic deduction. 
More precisely, for exact conditional constraint trees, we presented a local approach
that runs in linear time in the size of the conditional constraint trees.
For general conditional constraint trees, we introduced a global approach 
that runs in polynomial time in the size of the conditional constraint trees.

Probabilistic deduction in conditional constraint trees is motivated by
previous work in the literature on inference rules.
It generalizes patterns of commonsense reasoning that have 
been thoroughly studied in this work. 
Hence, we presented a new class of tractable probabilistic deduction problems, 
which are driven by artificial intelligence applications.

It is also important to note that the deduction process in exact and general conditional constraint trees can easily be 
elucidated in a graphical way. For example, the computation of the tight 
answer to the premise-restricted complete query $\exists\urule{{\sf M}}{x_1,x_2}{{\sf QRSTU}}$
to the exact conditional constraint tree in Fig.~\ref{diss53++}, left side, 
can be illustrated by labeling each node of the directed tree in Fig.~\ref{diss11++} 
with the corresponding tightest bounds of Table~\ref{TABlllPPP}.  

Like Bayesian networks, conditional constraint trees are well-structured probabilistic knowledge bases
that have an intuitive graphical representation. Differently from Bayesian networks, 
conditional constraint trees do not encode any probabilistic independencies. 
Thus, they can also be understood as a complement to Bayesian networks, useful for restricted 
applications in which well-structured independencies do not hold or are difficult to access.

Conditional constraint trees are quite restricted in their expressive power. 
However, in more general probabilistic knowledge bases, probabilistic deduction in 
conditional contraint trees may always act as local inference rules. 
For example, in case we desire explanatory information on some specific
local deductions from a subset of the whole knowledge base
(which could especially be useful in the design phase of a probabilistic knowledge base).

An important conclusion of this paper concerns the question whether to perform
probabilistic deduction by the iterative application of inference rules or by linear 
programming. The techniques of this paper have been elaborated by following the idea of inference rules 
in probabilistic deduction. Hence, on the one hand, this paper shows 
that the idea of inference rules can indeed bring us to efficient techniques for 
globally complete probabilistic deduction in restricted settings. 
However, on the other hand, 
given the technical complexity of the corresponding proofs, it seems unlikely that 
these results can be extended to probabilistic knowledge bases that are significantly 
more general than conditional constraint trees. 

That is, as far as significantly more general probabilistic deduction problems with conditional constraints are 
concerned, the iterative application of inference rules
does not seem to be very promising for globally complete probabilistic deduction. 
Note that a similar conclusion is drawn in a companion paper (1998a, 1999a), which 
shows the limits of locally complete inference rules for probabilistic deduction 
under taxonomic knowledge.

For example, probabilistic deduction from 
probabilistic logic programs that do not assume probabilistic independencies 
(Ng \& Subrahmanian 1993, 1994; Lukasiewicz, 1998d) 
should better not be done by the iterative application of inference rules.   
Note that much more promising techniques are, for example, 
global techniques by linear programming (Lukasiewicz, 1998d) and 
in particular approximation techniques based on truth-functional 
many-valued logics (Lukasiewicz 1998b, 1999b).

\vbox{\acks{I am very grateful to Michael Wellman and the referees for their useful comments.
I also want to thank Thomas Eiter for valuable comments on an earlier 
version of this paper. This paper is an extended and revised version 
of a paper that appeared in
{\em Principles of Knowledge Representation and Reasoning:\hspace*{-1pt}
 Proceedings of the 6th} \mbox{{\em International \hspace*{-1pt}Conference}, 
 \hspace*{-0.5pt}\BPGS\ 380--391.}\hspace*{-1.7pt}}}

\appendix
\section*{Appendix A. Preliminaries of the Proofs for Sections~\ref{AAAA} to \ref{QUERYY}}
\setcounter{section}{1}\label{appa}

In this section, we make some technical preparations for the proofs of 
Theorems~\ref{satzBLB2}, \ref{GRAPHU}, \ref{NEUT}, \ref{Theorem48}, and \ref{Theorem49}.
In the sequel, we use the notation
\begin{displaymath}\baq{cc|c}x_{1,1} &\ x_{1,2}\ &\ r_1 \\
              x_{2,1} & x_{2,2}&\ r_2 \\[0.9ex]\hline
              c_1 & c_2 & \eaq\end{displaymath}
as an abbreviation of the following system of equations:
\begin{equation}\label{magic}
\baq{lll}x_{1,1} + x_{1,2}&=&r_1\\x_{2,1} + x_{2,2}&=&r_2\\\eaq\ \ \ 
 \baq{lll}x_{1,1} + x_{2,1}&=&c_1\\x_{1,2} + x_{2,2}&=&c_2\ .\\\eaq
\end{equation}

The next lemma provides the optimal values of two linear programs 
%related to (\ref{magic}). These linear programs are the only ones
to be solved in the proofs of Theorems~\ref{satzBLB2}, \ref{GRAPHU}, \ref{NEUT}, \ref{Theorem48},
\mbox{and \ref{Theorem49}}.
%
\ble \label{MAGIC}
Let $r_1,r_2,c_1,c_2\ge 0$ with $r_1+r_2=c_1+c_2$. For all $i,j\in\{1,2\}$:

\medskip
\noindent a) $\min(r_i,c_j)\ =\  \max\ x_{i,j}$ subject to (\ref{magic}) and $x_{n,m}\ge 0$ for all $n,m\in\{1,2\}$.

\medskip
\noindent b) $\max(0,r_i-c_{3-j})\ =\ \min\ x_{i,j}$ subject to (\ref{magic}) and $x_{n,m}\ge 0$ for all $n,m\in\{1,2\}$.
\ele
%
%
{\bf Proof.} The claims can easily be verified (Lukasiewicz, 1996). $\Box$

\medskip
Let us assume that a conditional constraint tree is the union of two subtrees that have 
just one node in common. A model of each subtree and a third model related to the common node 
can now be combined to a model of the whole conditional constraint tree. This important 
result follows from the next lemma. 
%
\ble \label{COMMM}
Let ${\cal B}_1$ and ${\cal B}_{2}$ be sets of basic events with ${\cal B}_1\cap {\cal B}_2=\emptyset$.
Let $B_0$ be a new basic event that is not contained in ${\cal B}_1\cup {\cal B}_2$. 
Let ${\it Pr}_1$ and ${\it Pr}_2$ be probabilistic interpretations on the atomic events over ${\cal B}_1\cup\{B_0\}$ 
and ${\cal B}_2\cup\{B_0\}$, respectively.
Let $B_1$ and $B_2$ be conjunctive events over ${\cal B}_1$ and ${\cal B}_2$, respectively.
Let ${\it Pr}_0$ be a probabilistic interpretation on the atomic events over $\{B_0,B_1,B_2\}$ with
${\it Pr}_0({\it H_0 H_1})={\it Pr}_1({\it H_0 H_1})$ and
${\it Pr}_0({\it H_0 H_2})={\it Pr}_2({\it H_0 H_2})$
for all atomic events $H_0$, $H_1$, and $H_2$ over 
$\{B_0\}$, $\{B_1\}$, and $\{B_2\}$, respectively.

There is a probabilistic interpretation ${\it Pr}$ on the atomic events over ${\cal B}_1\cup{\cal B}_2\cup\{B_0\}$ with:
\begin{equation}\label{XCOMMM}
\baq{c}{\it Pr}({\it H_0 H_1 H_2})={\it Pr}_0({\it H_0 H_1 H_2}),\\[0.5ex]
{\it Pr}({\it H_0 A_1})={\it Pr}_1({\it H_0 A_1}),\text{ and }
{\it Pr}({\it H_0 A_2})={\it Pr}_2({\it H_0 A_2})\eaq
\end{equation}
for all atomic events $H_0$, $H_1$, $H_2$, $A_1$, and $A_2$ over the sets of basic events $\{B_0\}$, $\{B_1\}$, $\{B_2\}$,
${\cal B}_1$, and ${\cal B}_2$, respectively.
\ele
%
%
{\bf Proof.} Let the probabilistic interpretation ${\it Pr}$ on the atomic events over 
${\cal B}_1\cup{\cal B}_2\cup\{B_0\}$ be defined as follows:
\begin{displaymath}\mbox{${\it Pr}({\it H_0 A_1 A_2})=
\begin{cases}{\it Pr}_0({\it H_0 H_1H_2})\cdot\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}
\cdot\frac{{\it Pr}_2({\it H_0 A_2})}{{\it Pr}_2({\it H_0 H_2})}& \text{if $\,{\it Pr}_1({\it H_0 H_1})\cdot{\it Pr}_2({\it H_0 H_2})>0$}\vspace*{1ex}\cr
             0 & \text{if $\,{\it Pr}_1({\it H_0 H_1})\cdot{\it Pr}_2({\it H_0 H_2})=0$}\end{cases}$}\end{displaymath}
for all atomic events $H_0$, $A_1$, and $A_2$ over $\{B_0\}$, ${\cal B}_1$, 
and ${\cal B}_2$, respectively, with atomic events $H_1$ over $\{B_1\}$ and $H_2$ over $\{B_2\}$
such that $ A_1\Rightarrow{} H_1$ and $A_2\Rightarrow{} H_2$.

Now, we must show that ${\it Pr}$ satisfies (\ref{XCOMMM}). Let $H_0$, $H_1$, and $H_2$ be atomic events over $\{B_0\}$, $\{B_1\}$, and $\{B_2\}$, respectively.
For ${\it Pr}_1({\it H_0 H_1})>0$ and ${\it Pr}_2({\it H_0 H_2})>0$, we get:
\begin{displaymath}\baq{ccccc}{\it Pr}({\it H_0 H_1H_2})\!\!\!&=&\!\!\!\sum\limits_{\begin{Sb}
A_1\in{\cal A}_{{\cal B}_1},\,A_1\Rightarrow{} {\it H_1}\\
A_2\in{\cal A}_{{\cal B}_2},\,A_2\Rightarrow{} {\it H_2}\end{Sb}}{\it Pr}_0({\it H_0 H_1 H_2})\cdot
\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}\cdot\frac{{\it Pr}_2({\it H_0 A_2})}{{\it Pr}_2({\it H_0 H_2})}\,
\!\!\!&=&\!\!\!{\it Pr}_0({\it H_0 H_1H_2})\ .\!\!\\\eaq\end{displaymath}
For ${\it Pr}_1({\it H_0 H_1})=0$ or ${\it Pr}_2({\it H_0 H_2})=0$, we get 
${\it Pr}({\it H_0 H_1 H_2})=0={\it Pr}_0({\it H_0 H_1H_2})$.

Let $H_0$, $H_1$, and $A_1$ be atomic events over $\{B_0\}$, $\{B_1\}$, and ${\cal B}_1$, respectively, with $A_1 \Rightarrow{} H_1$.
For ${\it Pr}_1({\it H_0 H_1})>0$, ${\it Pr}_2({\it H_0 B_2})>0$, and ${\it Pr}_2({\it H_0 \ol{B}_2})>0$, it holds:
\begin{displaymath}\baq{ccccc}{\it Pr}({\it H_0 A_1})&=&
\phantom{+}\sum\limits_{A_2\in{\cal A}_{{\cal B}_2},\,A_2 \Rightarrow{} {\it B_2}}{\it Pr}_0({\it H_0 H_1 B_2})\cdot
\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}\cdot\frac{{\it Pr}_2({\it H_0 A_2})}{{\it Pr}_2({\it H_0 B_2})}&&\vspace*{1ex}\\
&&+\sum\limits_{A_2\in{\cal A}_{{\cal B}_2},\,A_2 \Rightarrow{} {\it \ol{B}_2}}{\it Pr}_0({\it H_0 H_1 \ol{B}_2})\cdot
\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}\cdot\frac{{\it Pr}_2({\it H_0 A_2})}{{\it Pr}_2({\it H_0 \ol{B}_2})}&&\vspace*{1ex}\\
&=&\phantom{+\sum\limits_{A_2\in{\cal A}_{{\cal B}_2},\,A_2 \Rightarrow{} {\it \ol{B}_2}}}
{\it Pr}_0({\it H_0 H_1})\cdot\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}&=&
{\it Pr}_1({\it H_0 A_1})\ .\!\!\!\!\eaq\end{displaymath}
For ${\it Pr}_1({\it H_0 H_1})>0$, ${\it Pr}_2({\it H_0 B_2})>0$, and ${\it Pr}_2({\it H_0 \ol{B}_2})=0$, we get:
\begin{displaymath}\baq{ccccc}{\it Pr}({\it H_0 A_1})&=&
\phantom{+}\sum\limits_{A_2\in{\cal A}_{{\cal B}_2},\,A_2 \Rightarrow{} {\it B_2}}{\it Pr}_0({\it H_0 H_1 B_2})\cdot
\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}\cdot\frac{{\it Pr}_2({\it H_0 A_2})}{{\it Pr}_2({\it H_0 B_2})}&&\vspace*{1ex}\\
&=&\phantom{+\sum\limits_{A_2\in{\cal A}_{{\cal B}_2},\,A_2 \Rightarrow{} {\it B_2}}}{\it Pr}_0({\it H_0 H_1})\cdot\frac{{\it Pr}_1({\it H_0 A_1})}{{\it Pr}_1({\it H_0 H_1})}&=&
{\it Pr}_1({\it H_0 A_1})\ .\!\!\!\vspace*{-1.5ex}\\\eaq\end{displaymath}
The proof is similar for ${\it Pr}_1({\it H_0 H_1})>0$, ${\it Pr}_2({\it H_0 B_2})=0$, and ${\it Pr}_2({\it H_0 \ol{B}_2})>0$.

\noindent For ${\it Pr}_1({\it H_0 H_1})=0$, we get ${\it Pr}({\it H_0 A_1})=0={\it Pr}_1({\it H_0 A_1})$.

Finally, the proof of ${\it Pr}({\it H_0 A_2})={\it Pr}_2({\it H_0 A_2})$ for all atomic events 
$H_0$ over $\{B_0\}$ and $A_2$ over ${\cal B}_2$ can be done analogously. $\Box$   

\section*{Appendix B. Proofs for Section~\ref{AAAA}}
\setcounter{section}{2}\label{appb}  
In this section, we give the proofs of Theorems~\ref{satzBLB2} and \ref{GRAPHU}. That is, 
we show the global soundness and the global completeness of the functions 
${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$. 
The proofs are done by induction on the recursive definition of ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, 
${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$. 

To prove global soundness, we just have to show the local soundness of the
computations in {\sc Leaf}, {\sc Chaining}, and {\sc Fusion}. 
To prove global completeness, we construct two models
of the conditional constraint tree, one related to the greatest lower bound
and another one related to the least upper bound
computed in {\sc Leaf}, {\sc Chaining}, and {\sc Fusion}.

For {\sc Leaf}, such a model is trivially given.
For {\sc Chaining}, we combine a model of the arrow, a model of the subtree, 
and a model connected  to the common node
to a model of the extended conditional constraint tree.  For {\sc Fusion},
we combine models of the subtrees and a model connected to the common node
to a model of the extended conditional constraint tree.
More precisely, for {\sc Chaining} and {\sc Fusion}, the models of the subtrees
are related to previously computed tightest bounds, 
while the model connected  to the common node
is related to the tightest bounds computed in the running {\sc Chaining} or {\sc Fusion}. 

We need the following technical preparations. 
The next lemma helps us to show the global completeness of 
the functions ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$ 
in {\sc Chaining} and {\sc Fusion}.
%
\ble \label{magic1I}
a) For all real numbers $u,v\in(0,1]$, $x_2\in[0,1]$, and $\ol{x}_2,z_2\in[0,\infty)$ with 
$x_2,\ol{x}_2\le z_2$ and $z_2\le x_2+\ol{x}_2$, there is some $x\in[z_2-\ol{x}_2,x_2]$ with:
\begin{equation}\label{Xmagic1I}\baq{lll}\min(1,\frac{uz_2}{v},1-u+\frac{ux}{v},u-\frac{ux}{v}+\frac{uz_2}{v})&=&
\min(1,\frac{uz_2}{v},1-u+\frac{ux_2}{v},u+\frac{u\ol{x}_2}{v})\ .\hspace*{-10ex}\eaq\end{equation}

\medskip
\noindent b) For $v_2,x_2\in[0,1]$ and $\ol{v}_2,\ol{x}_2,w_2,z_2\in[0,\infty)$ with $v_2\le w_2$, 
$\ol{v}_2\le w_2$, $x_2\le z_2$, $\ol{x}_2\le z_2$, $w_2\le v_2+\ol{v}_2$,
and $z_2\le x_2+\ol{x}_2$, there is $v\in[w_2-\ol{v}_2,v_2]$ and $x\in[z_2-\ol{x}_2,x_2]$ with:
\begin{equation}\label{Xmagic2I}
\baq{rcl}
\min(w_2,z_2,v+z_2-x,x+w_2-v)&=&\min(w_2,z_2,v_2+\ol{x}_2,x_2+\ol{v}_2)\hspace*{-6ex}\\
\min(v,x)&=&\min(v_2,x_2)\ .\eaq
\end{equation}
\ele
%
{\bf Proof.} The claims can easily be verified (Lukasiewicz, 1996). $\Box$

\medskip
The following lemma helps us to prove the local soundness and the local completeness
of the functions ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and 
${\it H}^{\gamma}_2$ in {\sc Chaining} and {\sc Fusion}. 
%
%
%
\ble \label{magic1}
a) Let $u,v\in(0,1]$, $x\in[0,1]$, and $\ol{x}\in[0,\infty)$. 
For all probabilistic interpretations ${\it Pr}$ with ${\it Pr}({\it B})>0$,
the conditions $u\cdot{\it Pr}(B )={\it Pr}({\it B C})$, $v\cdot{\it Pr}(C)={\it Pr}({\it B C})$, 
$x\cdot{\it Pr}(C)={\it Pr}({\it CL(C^{\uparrow}) })$,
and $\ol{x}\cdot{\it Pr}(C)={\it Pr}({\it \ol{C}L(C^{\uparrow}) })$ are equivalent to:

\bigskip
\noindent\phantom{.}\hfill$\baq{cc|c}\frac{{\it Pr}(\ol{B}\,\ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(B)}&\ \frac{{\it Pr}(\ol{B}\,\ol{C}L(C^{\uparrow}) )}{{\it Pr}(B )}\ &\  \frac{{\it Pr}(\ol{B}\,\ol{C})}{{\it Pr}(B)}\\[1.3ex] 
                   \frac{{\it Pr}(B \ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(B )}&\frac{{\it Pr}({\it B \ol{C}L(C^{\uparrow}) })}{{\it Pr}(B )}& 1-u\\[1.5ex]\hline
                   &&\\[-3ex]
                    \frac{{\it Pr}(\ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(B)} &\frac{u\ol{x}}{v}& \\\eaq$ \hfill
$\baq{cc|c}\frac{{\it Pr}(\ol{B} C\ol{L(C^{\uparrow})} )}{{\it Pr}(B )}&\ \frac{{\it Pr}(\ol{B} {\it CL(C^{\uparrow}) })}{{\it Pr}(B )}\ &\  \frac{u}{v}-u\\[1.3ex]
                   \frac{{\it Pr}({\it B C}\ol{L(C^{\uparrow})} )}{{\it Pr}(B )}&\frac{{\it Pr}({\it B CL(C^{\uparrow}) })}{{\it Pr}(B )}& u\\[1.5ex]\hline 
                   &&\\[-3ex]
                    \frac{u}{v}-\frac{ux}{v} &\frac{ux}{v}& \eaq$\hfill\phantom{.}

\bigskip
\noindent b) Let $v,x\in[0,1]$ and \mbox{$\ol{v},\ol{x}\in[0,\infty)$.}
For all probabilistic interpretations ${\it Pr}$ with
${\it Pr}({\it B})>0$, the conditions $v\cdot{\it Pr}(B)={\it Pr}({\it BL(G) })$, $\ol{v}\cdot{\it Pr}(B)={\it Pr}({\it \ol{B}L(G) })$, 
$x\cdot{\it Pr}(B)={\it Pr}({\it BL(H) })$, and $\ol{x}\cdot{\it Pr}(B)={\it Pr}({\it \ol{B}L(H) })$ are equivalent to:

\bigskip
\noindent\phantom{.}\hfill$\baq{cc|c}\frac{{\it Pr}(\ol{B}\,\ol{L(G)}\,\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}(\ol{B}\,\ol{L(G)} L(H) )}{{\it Pr}(B)}\ &\  \frac{{\it Pr}(\ol{B}\,\ol{L(G)} )}{{\it Pr}(B)}\\[1.3ex] 
                   \frac{{\it Pr}(\ol{B}L(G)\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}({\it \ol{B}L(G) L(H) })}{{\it Pr}(B)}\ &\  \ol{v}\\[1.5ex]\hline
                   &&\\[-3ex]
                    \frac{{\it Pr}(\ol{B}\,\ol{L(H)})}{{\it Pr}(B)} &\ \ol{x}& \\\eaq$ \hfill
$\baq{cc|c}\frac{{\it Pr}(B\ol{L(G)}\,\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}(B\ol{L(G)} {\it L(H) })}{{\it Pr}(B)}\  &\  1-v\\[1.3ex]
                   \frac{{\it Pr}({\it BL(G)}\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}({\it BL(G) L(H) })}{{\it Pr}(B)}\ &\  v\\[1.5ex]\hline 
                   &&\\[-3ex]
                    1-x &\ x& \eaq$\hfill\phantom{.}
\ele
%

\medskip
\noindent{\bf Proof.} The claims can be verified by straightforward arithmetic transformations
based on the properties of probabilistic interpretations. $\Box$

\medskip
After these preparations, we are now ready to prove the global soundness and the global completeness
of the functions ${\it H}^{\alpha}_1$, ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$.

\medskip
\noindent{\bf Proof of Theorem~\ref{satzBLB2}.} The claims are proved by induction on the 
recursive definition of ${\it H}^{\alpha}_1$. The case $C=B_1\ldots B_k$ is tackled
by iteratively splitting $C$ into two conjunctive events. Thus, it is
reduced to $C=GH$ with conjunctive events $G$ and $H$ that are disjoint 
in their basic events.
For $C\!=\!B_1$, we define $u={\it Pr}(C|B)$, $v={\it Pr}(B|C)$, and
$x_1 = {\it H}^{\alpha}_1(C,C^{\uparrow})$. 
For $C=B_1\ldots B_k$, hence $C={\it GH}$, let 
$v_1 = {\it H}^{\alpha}_1(B,G)$ and $x_1 = {\it H}^{\alpha}_1(B,H)$.

\medskip
\noindent a) All models ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(B)=0$ satisfy the indicated condition. 
In the sequel, let ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(B)>0$.

\medskip
\noindent {\it Basis:} Let $C=B$. Since $C=L(C)$, we get:
\begin{displaymath}\baq{lllllll}
\alpha_1\cdot{\it Pr}(B)&=&1\cdot{\it Pr}(B)&=& {\it Pr}({\it BC})&=&{\it Pr}(BL(C))\ .\\\eaq\end{displaymath}
{\it Induction:} Let  $C=B_1$.  For all models ${\it Pr}_2\in{\it Mo}(C,C^{\uparrow})$, 
we get by the induction hypothesis $x_1\cdot{\it Pr}_2(C)\le {\it Pr}_2(CL(C^{\uparrow}))$.
Thus, ${\it Pr}$ satisfies the same conditions. Since $L(C^{\uparrow})=L(C)$ and by Lemmata~\ref{MAGIC} 
and \ref{magic1}~a), we then get:
\begin{displaymath}\baq{lllllll}\alpha_1\cdot{\it Pr}(B)&=&\max(0,u-\frac{u}{v}+\frac{ux_1}{v})\cdot{\it Pr}(B)&\le&{\it Pr}(BL(C^{\uparrow})) &=&{\it Pr}(BL(C))\ .\\\eaq\end{displaymath}

Let $C$$\,=$$\,{\it GH}$. For all ${\it Pr}_1$$\,\in $$\,{\it Mo}(B,G)$
and ${\it Pr}_2$$\,\in$$\, {\it Mo}(B,H)$, we get by the induction hypothesis
$v_1\cdot{\it Pr}_1(B)\le {\it Pr}_1(BL(G))$ and $x_1\cdot{\it Pr}_2(B)\le {\it Pr}_2(BL(H))$.
Thus, ${\it Pr}$ satisfies the same conditions.
Since $L(G)L(H)=L(GH)=L(C)$ and by Lemmata~\ref{MAGIC} and \ref{magic1}~b):
\begin{displaymath}\baq{lllll}\max(0,v_1+x_1-1)\cdot{\it Pr}(B)&\le&{\it Pr}(BL(G)L(H)) &=&{\it Pr}(BL(C))\ .\\\eaq\end{displaymath}
b) 

\medskip
\noindent {\it Basis:} Let $C$$\,=$$\,B$. A model 
${\it Pr}$$\,\in$$\,{\it Mo}(B,C)$ such that ${\it Pr}(B)$$\,>$$\,0$, 
$1\cdot {\it Pr}(B)$$\,=$$\,\alpha_1\cdot {\it Pr}(B)={\it Pr}(BL(C))$, and $\Pr(\ol{B}L(C))=0$ 
is given by $\ol{B},B\mapsto 0,1$.

\medskip
\noindent {\it Induction:} Let  $C=B_1$. Let the model 
${\it Pr}_1$ of $\{\urule{B}{u,u}{C},
\urule{C}{v,v}{B}\}$ with ${\it Pr}_1(B)$$\,>$$\,0$ and ${\it Pr}_1(C)>0$ 
be defined like in the proof of Theorem~\ref{Doll}.

We now choose an appropriate model $\Pr_2\in {\it Mo}(C,C^{\uparrow})$.
Let us first consider the case $x_1$$\,>$$\,0$, $v$$\,=$$\,1$, or not $L(C^{\uparrow})$$\,\Rightarrow $$\,C$.
By the induction hypothesis, there exists a model
${\it Pr}_2$$\,\in$$\, {\it Mo}(C,C^{\uparrow})$ with ${\it Pr}_2(C)>0$,
$x_1\cdot {\it Pr}_2(C)={\it Pr}_2(CL(C^{\uparrow}))$, and 
$\Pr_2(\ol{C}L(C^{\uparrow}))=0$ iff $L(C^{\uparrow})$$\,\Rightarrow$$\,C$.
Let us  next assume $x_1$$\,=$$\,0$, $v$$\,<$$\,1$, and $L(C^{\uparrow})$$\,\Rightarrow $$\,C$. 
By Theorem~\ref{Doll}, there exists a 
model $\Pr_2''\in{\it Mo}(C,C^{\uparrow})$ with $\Pr_2''(CL(C^{\uparrow}))>0$. 
By the induction hypothesis, there exists a model  
${\it Pr}'_2$$\,\in$$\, {\it Mo}(C,C^{\uparrow})$ with ${\it Pr}'_2(C)>0$ and
$0\cdot {\it Pr}'_2(C)={\it Pr}'_2(CL(C^{\uparrow}))$.
Hence, there exists a model  $\Pr_2\in{\it Mo}(C,C^{\uparrow})$ with $\Pr_2(C)>0$ and 
\begin{displaymath}
\min(1-v,\Pr_2''(CL(C^{\uparrow}))\,/\,\Pr_2''(C))\cdot \Pr_2(C)=\Pr_2(CL(C^{\uparrow}))\ .
\end{displaymath}

By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(C)={\it Pr}_2(C)$ 
and ${\it Pr}_1(\ol{B}\,\ol{C})\ge {\it Pr}_2(\ol{C}L(C^{\uparrow}))$.
By Lemmata~\ref{MAGIC} and \ref{magic1}~a), we can choose the probabilistic interpretation 
${\it Pr}_0$ over $\{B,C,L(C^{\uparrow})\}$ with ${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ 
and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,C\}$ 
and $\{C,L(C^{\uparrow})\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(B\ol{C}L(C^{\uparrow}))&=&
\max(0,{\it Pr}_2(\ol{C}L(C^{\uparrow}))-{\it Pr}_1(\ol{B}\,\ol{C}))&=&0\\[0.2ex] 
{\it Pr}_0({\it BCL(C^{\uparrow})})&=&\max(0,{\it Pr}_2({C}L(C^{\uparrow}))-{\it Pr}_1(\ol{B}C))\ .\!\!&&\\\eaq
\end{displaymath} 

By Lemma~\ref{COMMM} with ${\cal B}_1=\{B\}$, ${\cal B}_2={\cal B}(C,C^{\uparrow})\setminus\{C\}$, 
$B_0=C$, $B_1=B$, and $B_2=L(C^{\uparrow})$, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$. 
By Lemma~\ref{magic1}~a), we get:
\begin{displaymath}\baq{lllllll}\alpha_1\cdot{\it Pr}(B)&=&\max(0,u-\frac{u}{v}+\frac{ux_1}{v})\cdot{\it Pr}(B)&=&{\it Pr}(BL(C^{\uparrow}))&=& {\it Pr}(BL(C))\ .\\\eaq\end{displaymath}
Moreover, it is easy to see that $\Pr(\ol{B}L(C))=0$ iff $L(C)$$\,\Rightarrow$$\,B$.

Let $C={\it GH}$. By the induction hypothesis, there are models ${\it Pr}_1\in {\it Mo}(B,G)$ 
and ${\it Pr}_2\in {\it Mo}(B,H)$ with ${\it Pr}_1(B)>0$, ${\it Pr}_2(B)>0$, 
$v_1\cdot {\it Pr}_1(B)={\it Pr}_1(BL(G))$, $x_1\cdot{\it Pr}_2(B)={\it Pr}_2(BL(H))$, 
$\Pr_1(\ol{B}L(G))=0$ iff $L(G)$$\,\Rightarrow$$\,B$, and $\Pr_2(\ol{B}L(H))=0$ iff $L(H)$$\,\Rightarrow$$\,B$.

By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(B)={\it Pr}_2(B)$
and ${\it Pr}_1(\ol{B}\,\ol{L(G)})\ge {\it Pr}_2(\ol{B}L(H)$.
By Lemmata~\ref{MAGIC} and \ref{magic1}~b), we can choose the probabilistic interpretation ${\it Pr}_0$ over $\{B,L(G),L(H)\}$ with
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,L(G)\}$ 
and $\{B,L(H)\}$, respectively, such that:
\begin{displaymath}\baq{lll}
{\it Pr}_0(\ol{B}L(G)L(H))&=&\min({\it Pr}_2(\ol{B}L(H)),{\it Pr}_1(\ol{B}L(G))\\[0.2ex]
{\it Pr}_0(BL(G)L(H))&=&\max(0,{\it Pr}_2(BL(H))-{\it Pr}_1(B\ol{L(G)}))\ .\\\eaq\end{displaymath} 

By Lemma~\ref{COMMM} with ${\cal B}_1={\cal B}(B,G)\setminus\{B\}$, ${\cal B}_2={\cal B}(B,H)\setminus\{B\}$, 
$B_0=B$, $B_1=L(G)$, and $B_2=L(H)$, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
By Lemma~\ref{magic1}~b), we get:
\begin{displaymath}
\baq{lllll}\max(0,v_1+x_1-1)\cdot{\it Pr}(B)&=&{\it Pr}(BL(G)L(H)) &=&{\it Pr}(BL(C))\ .\\\eaq
\end{displaymath} 
Moreover, it is easy to see that $\Pr(\ol{B}L(C))=0$ iff $L(C)$$\,\Rightarrow$$\,B$. $\Box$

\bigskip
\noindent {\bf Proof of Theorem~\ref{GRAPHU}.} The claims are proved by induction on the 
recursive definition of ${\it H}^{\alpha}_2$, ${\it H}^{\beta}_2$, and ${\it H}^{\gamma}_2$. 
Again, the case $C=B_1\ldots B_k$ is tackled by iteratively splitting $C$ into two conjunctive events. 
Thus, it is reduced to $C=GH$ with conjunctive events $G$ and $H$ that are disjoint 
in their basic events.
For $C=B_1$ let $u={\it Pr}(C|B)$, $v={\it Pr}(B|C)$, and
\begin{displaymath}\baq{lll}
x_2 = {\it H}^{\alpha}_2(C,C^{\uparrow}),& \ol{x}_2 = {\it H}^{\beta}_2(C,C^{\uparrow}), & z_2 = {\it H}^{\gamma}_2(C,C^{\uparrow})\ .\\\eaq
\end{displaymath}
For $C=B_1\ldots B_k$, hence $C={\it GH}$, we define:
\begin{displaymath}\baq{lll}
v_2 = {\it H}^{\alpha}_2(B,G),& \ol{v}_2 = {\it H}^{\beta}_2(B,G), & w_2 = {\it H}^{\gamma}_2(B,G)\\
x_2 = {\it H}^{\alpha}_2(B,H),& \ol{x}_2 = {\it H}^{\beta}_2(B,H), & z_2 = {\it H}^{\gamma}_2(B,H)\ .\\\eaq
\end{displaymath}
a) For ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(B)=0$, we get ${\it Pr}(N)=0$ for all $N\in {\cal B}(B,C)$. Thus,
${\it Pr}$ satisfies the indicated conditions. Next, let ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(B)>0$.

\medskip
\noindent {\it Basis:} Let $C=B$. Since $L(C)=C$, we get:
\begin{displaymath}\baq{lllllll}{\it Pr}(BL(C))&=&{\it Pr}({\it BC}) &=& 1\cdot{\it Pr}(B)&=&\alpha_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(\ol{B}L(C))&=&{\it Pr}(\ol{B}C)&=&0\cdot{\it Pr}(B)&=&\beta_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&=&{\it Pr}(C)&=&1\cdot{\it Pr}(B)&=&\gamma_2\cdot{\it Pr}(B)\ .\\\eaq\end{displaymath}
{\it Induction:} Let  $C=B_1$.  For all models ${\it Pr}_2\in{\it Mo}(C,C^{\uparrow})$, 
we get by the induction hypothesis ${\it Pr}_2(CL(C^{\uparrow}))\le x_2\cdot{\it Pr}_2(C)$, 
${\it Pr}_2(\ol{C}L(C^{\uparrow}))\le \ol{x}_2\cdot{\it Pr}_2(C)$, and ${\it Pr}_2(L(C^{\uparrow}))\le z_2\cdot{\it Pr}_2(C)$.
Hence, ${\it Pr}$ satisfies the same conditions.
Since $L(C)=L(C^{\uparrow})$ and by Lemmata~\ref{MAGIC} and \ref{magic1}~a), we then get:
\begin{displaymath}\baq{llllrll}{\it Pr}(BL(C))&\!\!=&\!\!{\it Pr}(BL(C^{\uparrow}))&\!\!\le&\!\! \min(1,\frac{uz_2}{v},1-u+\frac{ux_2}{v},u+\frac{u\ol{x}_2}{v})\cdot{\it Pr}(B)&\!\!=&\!\!\alpha_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(\ol{B}L(C))&\!\!=&\!\!{\it Pr}(\ol{B}L(C^{\uparrow}))&\!\!\le&\!\! \min(\frac{u\ol{x}_2}{v}+\frac{u}{v}-u,\frac{uz_2}{v})\cdot{\it Pr}(B)&\!\!=&\!\!\beta_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&\!\!=&\!\!{\it Pr}(L(C^{\uparrow}))&\!\!\le&\!\! \frac{uz_2}{v}\cdot{\it Pr}(B)&\!\!=&\!\!\gamma_2\cdot{\it Pr}(B)\ .\hspace*{-2ex}\\\eaq\end{displaymath}

Let $C={\it GH}$. For all models ${\it Pr}_1\in {\it Mo}(B,G)$
and all models ${\it Pr}_2\in {\it Mo}(B,H)$, we get by the induction hypothesis:
\begin{displaymath}\!\!\baq{llllll}{\it Pr}_1(BL(G))\!\!&\le&\!\! v_2\cdot{\it Pr}_1(B),\! & {\it Pr}_2(BL(H))\!\!&\le&\!\! x_2\cdot{\it Pr}_2(B)\\[0.2ex]
{\it Pr}_1(\ol{B}L(G))\!\!&\le&\!\! \ol{v}_2\cdot{\it Pr}_1(B),\! & {\it Pr}_2(\ol{B}L(H))\!\!&\le&\!\! \ol{x}_2\cdot{\it Pr}_2(B)\\[0.2ex]
{\it Pr}_1(L(G))\!\!&\le&\!\! w_2\cdot{\it Pr}_1(B),\!  & {\it Pr}_2(L(H))\!\!&\le&\!\! z_2\cdot{\it Pr}_2(B)\ .\\\eaq\hspace*{-4pt}\end{displaymath}
Thus, ${\it Pr}$ satisfies the same conditions.
Since $L(C)=L(GH)=L(G)L(H)$ and by Lemmata~\ref{MAGIC} and \ref{magic1}~b), we get:
\begin{displaymath}\baq{lllll}{\it Pr}(BL(C))&=&{\it Pr}(BL(G)L(H)) &\le& \min(v_2,x_2)\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(\ol{B}L(C))&=&{\it Pr}(\ol{B}L(G)L(H)) &\le& \min(\ol{v}_2,\ol{x}_2)\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&=&{\it Pr}(L(G)L(H)) &\le& \min(w_2,z_2,v_2+\ol{x}_2,x_2+\ol{v}_2)\cdot{\it Pr}(B)\ .\\\eaq\end{displaymath}
b) and c) 

\medskip
\noindent {\it Basis:} Let $C=B$. A model 
${\it Pr}\in{\it Mo}(B,C)$ with ${\it Pr}(B)>0$ satisfying 
${\it Pr}(BL(C))=1\cdot {\it Pr}(B)=\alpha_2\cdot{\it Pr}(B)$, 
${\it Pr}(\ol{B}L(C))=0\cdot {\it Pr}(B)=\beta_2\cdot{\it Pr}(B)$,
and ${\it Pr}(L(C))=1\cdot {\it Pr}(B)=\gamma_2\cdot{\it Pr}(B)$ is given by $\ol{B},B\mapsto 0,1$.

\medskip
\noindent {\it Induction:} Let  $C=B_1$. Let the model ${\it Pr}_1$ of $\{\urule{B}{u,u}{C},
\urule{C}{v,v}{B}\}$ with ${\it Pr}_1(B)>0$ and ${\it Pr}_1(C)>0$ be defined like in the proof of Theorem~\ref{Doll}.

For the proof of c), by the induction hypothesis, there is some
${\it Pr}_2$$\,\in$$\,{\it Mo}(C,C^{\uparrow})$ with ${\it Pr}_2(C)$$\,>$$\,0$,
${\it Pr}_2(\ol{C}L(C^{\uparrow}))=\ol{x}_2\cdot {\it Pr}_2(C)$,
and ${\it Pr}_2(L(C^{\uparrow}))=z_2\cdot {\it Pr}_2(C)$.

By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(C)={\it Pr}_2(C)$ 
and ${\it Pr}_1(\ol{B}\,\ol{C})\ge {\it Pr}_2(\ol{C}L(C^{\uparrow}))$.
By Lemma~\ref{MAGIC}, we can choose the probabilistic interpretation 
${\it Pr}_0$ over $\{B,C,L(C^{\uparrow})\}$ with ${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ 
and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,C\}$ 
and $\{C,L(C^{\uparrow})\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(\ol{B}\,\ol{C}L(C^{\uparrow}))&=&\min({\it Pr}_1(\ol{B}\,\ol{C}),{\it Pr}_2(\ol{C}L(C^{\uparrow})))&=&{\it Pr}_2(\ol{C}L(C^{\uparrow}))\\[0.2ex] 
{\it Pr}_0({\it \ol{B}CL(C^{\uparrow})})&=&\min({\it Pr}_1(\ol{B}C),{\it Pr}_2({C}L(C^{\uparrow})))\ .\!\!&&\\\eaq\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1=\{B\}$, ${\cal B}_2={\cal B}(C,C^{\uparrow})\setminus\{C\}$, 
$B_0=C$, $B_1=B$, and $B_2=L(C^{\uparrow})$, there is a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). 
Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$. By Lemma~\ref{magic1}~a), we get:
\begin{displaymath}\baq{llllrll}{\it Pr}(\ol{B}L(C))&=& {\it Pr}(\ol{B}L(C^{\uparrow}))&=&\min(\frac{u\ol{x}_2}{v}+\frac{u}{v}-u,\frac{uz_2}{v})\cdot{\it Pr}(B)&=&\beta_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&=& {\it Pr}(L(C^{\uparrow}))&=&\frac{uz_2}{v}\cdot{\it Pr}(B)&=&\gamma_2\cdot{\it Pr}(B)\ .\\\eaq\end{displaymath}
\indent For the proof of b), by the induction hypothesis, there are models ${\it Pr}_{1,2}\,,{\it Pr}_{2,2}\in {\it Mo}(C,C^{\uparrow})$ with ${\it Pr}_{1,2}(C)>0$, 
\mbox{${\it Pr}_{2,2}(C)>0$}, and
\begin{equation}\label{KKKL1}
\baq{ll} {\it Pr}_{1,2}(CL(C^{\uparrow}))=x_2\cdot {\it Pr}_{1,2}(C),\!  &{\it Pr}_{1,2}(L(C^{\uparrow}))=z_2\cdot {\it Pr}_{1,2}(C)\\[0.2ex] 
{\it Pr}_{2,2}(\ol{C}L(C^{\uparrow}))=\ol{x}_2\cdot {\it Pr}_{2,2}(C),\!  &{\it Pr}_{2,2}(L(C^{\uparrow}))=z_2\cdot {\it Pr}_{2,2}(C)\ .\\\eaq
\end{equation}
These conditions already entail $x_2\le z_2$ and $\ol{x}_2\le z_2$.
With the results from a), we additionally get $z_2\le x_2+\ol{x}_2$.
By Lemma~\ref{magic1I}~a), there is $x\in[z_2-\ol{x}_2,x_2]$ with (\ref{Xmagic1I}).
By (\ref{KKKL1}), there is ${\it Pr}_2\in {\it Mo}(C,C^{\uparrow})$ with ${\it Pr}_2(C)>0$ and
\begin{displaymath}\baq{ll} {\it Pr}_2(CL(C^{\uparrow}))=x\cdot {\it Pr}_2(C),\!  &{\it Pr}_2(L(C^{\uparrow}))=z_2\cdot {\it Pr}_2(C)\ .\\\eaq\end{displaymath}
\indent By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(C)={\it Pr}_2(C)$.
By Lemma~\ref{MAGIC}, we can choose the probabilistic interpretation 
${\it Pr}_0$ over $\{B,C,L(C^{\uparrow})\}$ with ${\it Pr}_0(A_1)$ $=$ ${\it Pr}_1(A_1)$ 
and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,C\}$ 
and $\{C,L(C^{\uparrow})\}$, respectively, such that:
\begin{displaymath}\baq{lll}{\it Pr}_0(B\ol{C}L(C^{\uparrow}))&=&\min({\it Pr}_1(B\ol{C}),{\it Pr}_2(\ol{C}L(C^{\uparrow})))\\[0.2ex] 
{\it Pr}_0(BCL(C^{\uparrow}))&=&\min({\it Pr}_1({\it BC}),{\it Pr}_2({\it CL(C^{\uparrow})}))\ .\\\eaq\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1=\{B\}$, ${\cal B}_2={\cal B}(C,C^{\uparrow})\setminus\{C\}$, 
$B_0=C$, $B_1=B$, and $B_2=L(C^{\uparrow})$, there is a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). 
Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$. By Lemma~\ref{magic1}~a), we get:
\begin{displaymath}\baq{llllrll}{\it Pr}(BL(C))&\!\!=&\!\!{\it Pr}(BL(C^{\uparrow}))&\!\!=&\!\!\min(1,\frac{uz_2}{v},1-u+\frac{ux_2}{v},u+\frac{u\ol{x}_2}{v})\cdot{\it Pr}(B)&\!\!=&\!\!\alpha_2\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&\!\!=&\!\!{\it Pr}(L(C^{\uparrow}))&\!\!=&\!\! \frac{uz_2}{v}\cdot{\it Pr}(B)&\!\!=&\!\!\gamma_2\cdot{\it Pr}(B)\ .\!\!\!\\\eaq\end{displaymath}
\indent Let $C={\it GH}$. We just show b), the claim in c) can be proved analogously.
%
By the induction hypothesis, there are models ${\it Pr}_{1,1}\,,{\it Pr}_{2,1}\in {\it Mo}(B,G)$ and ${\it Pr}_{1,2}\,,{\it Pr}_{2,2}\in {\it Mo}(B,H)$
with ${\it Pr}_{1,1}(B)>0$, ${\it Pr}_{2,1}(B)>0$, ${\it Pr}_{1,2}(B)>0$, ${\it Pr}_{2,2}(B)>0$, and
\begin{equation}\label{KKKL2}\baq{ll} {\it Pr}_{1,1}(BL(G))=v_2\cdot {\it Pr}_{1,1}(B),\!  &{\it Pr}_{1,1}(L(G))=w_2\cdot {\it Pr}_{1,1}(B)\\[0.2ex] 
{\it Pr}_{2,1}(\ol{B}L(G))=\ol{v}_2\cdot {\it Pr}_{2,1}(B),\!  &{\it Pr}_{2,1}(L(G))=w_2\cdot {\it Pr}_{2,1}(B)\\[0.2ex] 
{\it Pr}_{1,2}(BL(H))=x_2\cdot {\it Pr}_{1,2}(B),\!  &{\it Pr}_{1,2}(L(H))=z_2\cdot {\it Pr}_{1,2}(B)\\[0.2ex] 
{\it Pr}_{2,2}(\ol{B}L(H))=\ol{x}_2\cdot {\it Pr}_{2,2}(B),\!  &{\it Pr}_{2,2}(L(H))=z_2\cdot {\it Pr}_{2,2}(B)\ .\\\eaq\end{equation}
These conditions already entail $v_2\le w_2$, $\ol{v}_2\le w_2$, $x_2\le z_2$, and $\ol{x}_2\le z_2$.
With the results from a), we additionally get $w_2\le v_2+\ol{v}_2$ and $z_2\le x_2+\ol{x}_2$.
By Lemma~\ref{magic1I}~b), there is $v\in[w_2-\ol{v}_2,v_2]$ and $x\in[z_2-\ol{x}_2,x_2]$ with (\ref{Xmagic2I}).
By (\ref{KKKL2}), there is ${\it Pr}_1\in {\it Mo}(B,G)$ and ${\it Pr}_2\in {\it Mo}(B,H)$  with ${\it Pr}_1(B)>0$,
${\it Pr}_2(B)>0$, and
\begin{displaymath}\baq{ll} {\it Pr}_1(BL(G))=v\cdot {\it Pr}_1(B),\!  &{\it Pr}_1(L(G))=w_2\cdot {\it Pr}_1(B)\\[0.2ex] 
{\it Pr}_2(BL(H))=x\cdot {\it Pr}_2(B),\!  &{\it Pr}_2(L(H))=z_2\cdot {\it Pr}_2(B)\ .\\\eaq\end{displaymath}
\indent By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(B)={\it Pr}_2(B)$.
By Lemma~\ref{MAGIC}, we can choose the probabilistic interpretation ${\it Pr}_0$ over $\{B,L(G),L(H)\}$ with  
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,L(G)\}$ 
and $\{B,L(H)\}$, respectively, such that:
\begin{displaymath}\baq{lll}{\it Pr}_0({\it \ol{B}L(G)L(H)})&=&\min({\it Pr}_1(\ol{B}L(G)),{\it Pr}_2(\ol{B}L(H)))\\[0.2ex]
{\it Pr}_0({\it BL(G)L(H)})&=&\min({\it Pr}_1(BL(G)),{\it Pr}_2(BL(H)))\ .\\\eaq\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1={\cal B}(B,G)\setminus\{B\}$, ${\cal B}_2={\cal B}(B,H)\setminus\{B\}$, 
$B_0=B$, $B_1=L(G)$, and $B_2=L(H)$, there is a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
By Lemma~\ref{magic1}~b), we get:
\begin{displaymath}\baq{lllll}{\it Pr}(BL(C))&=& {\it Pr}(BL(G)L(H))&=&\min(v_2,x_2)\cdot{\it Pr}(B)\\[0.2ex]
{\it Pr}(L(C))&=&{\it Pr}(L(G)L(H))&=& 
\min(w_2,z_2,v_2+\ol{x}_2,x_2+\ol{v}_2)\cdot{\it Pr}(B)\ .\ \text{ $\Box$}\\\eaq
\end{displaymath} 

Finally, note that computing least upper bounds is more difficult than 
computing greatest lower bounds, since for each edge 
$B\rightarrow C$, by Lemmata \ref{Toll} and \ref{magic1} a), the greatest lower bound
of $\Pr(B\ol{C}L(C^{\uparrow}))/\Pr(B)$ subject to $\Pr$$\,\in$$\,{\it Mo}(B,C)$
and $\Pr(B)$$\,>$$\,0$ is always 0, but the least upper bound of $\Pr(B\ol{C}L(C^{\uparrow}))/\Pr(B)$ subject 
to $\Pr$$\,\in$$\,{\it Mo}(B,C)$ and $\Pr(B)$$\,>$$\,0$ is \mbox{generally not 1.}

\section*{Appendix C. Proofs for Section~\ref{SCRCQ}}
\setcounter{section}{3}\label{appc}
In this section, we give the proofs of Theorems~\ref{NEUT} and \ref{Theorem48}.

We need some technical preparations as follows. The next lemma helps us to show the local soundness
of the function ${\it H}^{\delta}_1$ in {\sc Fusion}.
% 
\ble \label{magic33+}   
For all real numbers $u_1,u,v_1,v,x_1,x,y_1,y\in(0,1]$ with $u_1\le u$, $v_1\le v$, $x_1\le x$, $y_1\le y$,
and $u_1+x_1>1$, it holds:
\[\baq{rcl}\min(u/v-u,\,x/y-x)\,/\,(u+x-1)
& \!\le\! & \min(u_1/v_1-u_1,\,x_1/y_1-x_1)\,/\,(u_1+x_1-1)\ .\\\eaq\]
\ele 
{\bf Proof.} The claim can easily be verified (Lukasiewicz, 1996). $\Box$

\medskip
The following lemma helps us to show the local soundness and the local completeness
of the function ${\it H}^{\delta}_1$ in {\sc Chaining} and {\sc Fusion}. 
%
\ble \label{magic1+}
a) Let $u$, $v$, $x$, and $y$ be real numbers from $(0,1]$. 
For all probabilistic interpretations ${\it Pr}$ with \mbox{${\it Pr}(L(C^{\uparrow}))>0$},
the conditions $u\cdot{\it Pr}(B )={\it Pr}({\it B C})$, $v\cdot{\it Pr}(C)={\it Pr}({\it B C})$, 
$x\cdot{\it Pr}(C)={\it Pr}({\it CL(C^{\uparrow}) })$, and
$y\cdot{\it Pr}(L(C^{\uparrow}))={\it Pr}({\it CL(C^{\uparrow}) })$ are equivalent to:

\bigskip
\noindent\phantom{.}\hfill$\baq{cc|c}\frac{{\it Pr}(\ol{B}\,\ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(L(C^{\uparrow}))}&\ \frac{{\it Pr}(\ol{B}\,\ol{C}L(C^{\uparrow}) )}{{\it Pr}(L(C^{\uparrow}))}\ &\  \frac{{\it Pr}(\ol{B}\,\ol{C})}{{\it Pr}(L(C^{\uparrow}))}\\[1.3ex] 
                   \frac{{\it Pr}(B \ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(L(C^{\uparrow}))}&\frac{{\it Pr}({\it B \ol{C}L(C^{\uparrow}) })}{{\it Pr}(L(C^{\uparrow}))}& \frac{yv}{xu}-\frac{yv}{x}\\[1.5ex]\hline
                   &&\\[-3ex]
                    \frac{{\it Pr}(\ol{C}\,\ol{L(C^{\uparrow})} )}{{\it Pr}(L(C^{\uparrow}))} &1-y& \\\eaq$ \hfill
$\baq{cc|c}\frac{{\it Pr}(\ol{B} C\ol{L(C^{\uparrow})} )}{{\it Pr}(L(C^{\uparrow}))}&\ \frac{{\it Pr}(\ol{B} {\it CL(C^{\uparrow}) })}{{\it Pr}(L(C^{\uparrow}))}\ &\  \frac{y}{x}-\frac{yv}{x}\\[1.3ex]
                   \frac{{\it Pr}({\it B C}\ol{L(C^{\uparrow})} )}{{\it Pr}(L(C^{\uparrow}))}&\frac{{\it Pr}({\it B CL(C^{\uparrow}) })}{{\it Pr}(L(C^{\uparrow}))}& \frac{yv}{x}\\[1.5ex]\hline 
                   &&\\[-3ex]
                    \frac{y}{x}-y &y& \eaq$\hfill\phantom{.}

\bigskip 
\noindent b) Let $u$, $v$, $x$, and $y$ be real numbers from $(0,1]$.
For all probabilistic interpretations ${\it Pr}$ with
${\it Pr}({\it B})>0$, the conditions $u\cdot{\it Pr}(B)={\it Pr}({\it BL(G) })$, $v\cdot{\it Pr}(L(G))={\it Pr}({\it BL(G) })$, 
$x\cdot{\it Pr}(B)={\it Pr}({\it BL(H) })$, and $y\cdot{\it Pr}(L(H))={\it Pr}({\it BL(H) })$ are equivalent to:

\bigskip
\noindent\phantom{.}\hfill$\baq{cc|c}\frac{{\it Pr}(\ol{B}\,\ol{L(G)}\,\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}(\ol{B}\,\ol{L(G)} L(H) )}{{\it Pr}(B)}\ &\  \frac{{\it Pr}(\ol{B}\,\ol{L(G)} )}{{\it Pr}(B)}\\[1.3ex] 
                   \frac{{\it Pr}(\ol{B}L(G)\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}({\it \ol{B}L(G) L(H) })}{{\it Pr}(B)}\ &\  \frac{u}{v}-u\\[1.5ex]\hline
                   &&\\[-3ex]
                    \frac{{\it Pr}(\ol{B}\,\ol{L(H)})}{{\it Pr}(B)} &\ \frac{x}{y}-x& \\\eaq$ \hfill
$\baq{cc|c}\frac{{\it Pr}(B\ol{L(G)}\,\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}(B\ol{L(G)} {\it L(H) })}{{\it Pr}(B)}\  &\  1-u\\[1.3ex]
                   \frac{{\it Pr}({\it BL(G)}\ol{L(H)} )}{{\it Pr}(B)}&\ \frac{{\it Pr}({\it BL(G) L(H) })}{{\it Pr}(B)}\ &\  u\\[1.5ex]\hline 
                   &&\\[-3ex]
                    1-x &\ x& \eaq$\hfill\phantom{.}
\ele
%

\medskip
\noindent{\bf Proof.} The claims can be verified by straightforward arithmetic transformations
based on the properties of probabilistic interpretations. $\Box$

\medskip
We are now ready to prove Theorems~\ref{NEUT} and \ref{Theorem48}.

\medskip
\noindent{\bf Proof of Theorem~\ref{NEUT}.} The claims are proved by induction on the 
recursive definition of $H^{\delta}_1$. The proof for $C=B_1 B_2\ldots B_k$ with 
$k>1$ is done for $k=2$. It can easily be generalized to $k\ge 2$.
For $C\!=\!B_1$, we define $u_1={\it Pr}_1(C|B)$, $v_1={\it Pr}_1(B|C)$,
$x_1 = {\it H}^{\alpha}_1(C,C^{\uparrow})$, and $y_1 = {\it H}^{\delta}_1(C,C^{\uparrow})$. 
Note that $\alpha_1>0$ entails $x_1,y_1>0$ and $v_1+x_1>1$.
For $C=B_1 B_2$, we define $G=B_1$, $H=B_2$, 
$u_1 = {\it H}^{\alpha}_1(B,G)$, $v_1 = {\it H}^{\delta}_1(B,G)$,
$x_1 = {\it H}^{\alpha}_1(B,H)$, and $y_1 = {\it H}^{\delta}_1(B,H)$.
Note that $\alpha_1>0$ entails $u_1,v_1,x_1,y_1>0$ and $u_1+x_1>1$.

\medskip
\noindent a) All models ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(L(C))=0$ satisfy the indicated condition. 
In the sequel, let ${\it Pr}\in {\it Mo}(B,C)$ with ${\it Pr}(L(C))>0$ and thus also ${\it Pr}(B)>0$.

\medskip
\noindent {\it Basis:} Let $C=B$. Since $C=L(C)$, we get:
\begin{displaymath}\baq{lllllll}
\delta_1\cdot{\it Pr}(L(C))&=&1\cdot{\it Pr}(L(C))&=& {\it Pr}(CL(C))&=&{\it Pr}(BL(C))\ .\\\eaq\end{displaymath}
{\it Induction:} Let  $C=B_1$.  For all models ${\it Pr}_2\in{\it Mo}(C,C^{\uparrow})$,
we get $x_1\cdot{\it Pr}_2(C)\le {\it Pr}_2(CL(C^{\uparrow}))$
by Theorem~\ref{LEM1}~a), and 
$y_1\cdot{\it Pr}_2(L(C^{\uparrow}))\le{\it Pr}_2(CL(C^{\uparrow}))$
by the induction hypothesis.
Thus, ${\it Pr}$ satisfies the same conditions. Since $L(C^{\uparrow})=L(C)$ and by 
Lemmata~\ref{MAGIC} and \ref{magic1+}~a):
\begin{displaymath}\baq{lllllllll}\delta_1&=&
y_1-\frac{y_1}{x_1}+\frac{y_1 v_1}{x_1}&\le&
{\it Pr}(CL(C^{\uparrow}))\,/\,{\it Pr}(L(C^{\uparrow})) &=
&{\it Pr}(CL(C))\,/\,{\it Pr}(L(C))\ .\\
\eaq\end{displaymath}
\indent Let $C={\it GH}$. For all models ${\it Pr}_1\in {\it Mo}(B,G)$
and ${\it Pr}_2\in {\it Mo}(B,H)$, we get by Theorem~\ref{LEM1}~a) and by the induction hypothesis, respectively:
\begin{displaymath}\!\!\baq{llllll}
u_1\cdot{\it Pr}_1(B)\!\!&\le&\!\!{\it Pr}_1(BL(G)),\! & x_1\cdot{\it Pr}_2(B)\!\!
&\le&\!\!{\it Pr}_2(BL(H))\\
v_1\cdot{\it Pr}_1(L(G))\!\!&\le&\!\!{\it Pr}_1(BL(G)),\! & y_1\cdot{\it Pr}_2(L(H))\!\!
&\le&\!\!{\it Pr}_2(BL(H))\ .\\
\eaq\hspace*{-4pt}\end{displaymath}
Hence, ${\it Pr}$ satisfies the same conditions.
Since $L(G)L(H)=L(GH)=L(C)$ and by Lemmata~\ref{MAGIC}, \ref{magic33+}, and \ref{magic1+}~b), we then get:
\begin{displaymath}\baq{lcccccl}
\delta_1&\!\!=\!\!&1\,/\,(1+\frac{\min(u_1/v_1-u_1,\,x_1/y_1-x_1)}{u_1+x_1-1})& \!\!\le\!\!
&1\,/\,(1+\frac{{\it Pr}(\ol{B}L(G)L(H))/{\it Pr}(B)}{{\it Pr}(BL(G)L(H))/{\it Pr}(B)}
)   &\!\!=\!\!&\frac{{\it Pr}(BL(C))}{{\it Pr}(L(C))}\ .\\
\eaq\end{displaymath}

\noindent b) 

\medskip
\noindent {\it Basis:} Let $C=B$. A model 
${\it Pr}\in{\it Mo}(B,C)$ such that ${\it Pr}(B)>0$, ${\it Pr}(L(C))>0$,
\mbox{$1\cdot {\it Pr}(L(C))={\it Pr}(BL(C))$}, and $1\cdot {\it Pr}(B)={\it Pr}(BL(C))$ 
is given by $\ol{B},B\mapsto 0,1$.

\medskip
\noindent {\it Induction:} Let  $C$$\,=$$\,B_1$. Let the model ${\it Pr}_1$ of $\{\urule{B}{u_1,u_1}{C},
\urule{C}{v_1,v_1}{B}\}$ with \mbox{${\it Pr}_1(B)$$\,>$$\,0$} and ${\it Pr}_1(C)>0$ be defined like in the proof of Theorem~\ref{Doll}.

By the induction hypothesis, there is
${\it Pr}_2$$\,\in$$\,{\it Mo}(C,C^{\uparrow})$ with ${\it Pr}_2(C)$$\,>$$\,0$, $\Pr_2(L(C^{\uparrow}))$$\,>$$\,0$,
\mbox{$y_1\cdot {\it Pr}_2(L(C^{\uparrow}))={\it Pr}_2(CL(C^{\uparrow}))$},
and $x_1\cdot {\it Pr}_2(C)={\it Pr}_2(CL(C^{\uparrow}))$.
By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ such that ${\it Pr}_1(C)={\it Pr}_2(C)$ 
and ${\it Pr}_1(\ol{B}\,\ol{C})\ge {\it Pr}_2(\ol{C}L(C^{\uparrow}))$.
By Lemmata~\ref{MAGIC} and \ref{magic1+}~a), we can choose the probabilistic interpretation 
${\it Pr}_0$ over $\{B,C,L(C^{\uparrow})\}$ with ${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ 
and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,C\}$ 
and $\{C,L(C^{\uparrow})\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(B\ol{C}L(C^{\uparrow}))&=&
\max(0,{\it Pr}_2(\ol{C}L(C^{\uparrow}))-{\it Pr}_1(\ol{B}\,\ol{C}))&=&0\\[0.2ex] 
{\it Pr}_0({\it BCL(C^{\uparrow})})&=&\max(0,{\it Pr}_2({C}L(C^{\uparrow}))-{\it Pr}_1(\ol{B}C))\ .\!\!&&\\\eaq
\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1=\{B\}$, ${\cal B}_2={\cal B}(C,C^{\uparrow})\setminus\{C\}$, 
$B_0=C$, $B_1=B$, and $B_2=L(C^{\uparrow})$, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). 
Hence, it holds ${\it Pr}\in{\it Mo}(B,C)$, ${\it Pr}(B)>0$, and $\Pr(L(C))>0$. 
Moreover, by Lemma~\ref{magic1+}~a), we get:
\begin{displaymath}\baq{lllllll}\delta_1&=&
y_1-\frac{y_1}{x_1}+\frac{y_1 v_1}{x_1}&=&
{\it Pr}(CL(C^{\uparrow}))\,/\,{\it Pr}(L(C^{\uparrow})) &=&{\it Pr}(CL(C))\,/\,{\it Pr}(L(C))\\[1ex]
\alpha_1&=&
u_1-\frac{u_1}{v_1}+\frac{u_1 x_1}{v_1}&=&
{\it Pr}(CL(C^{\uparrow}))\,/\,{\it Pr}(C) &=&{\it Pr}(CL(C))\,/\,{\it Pr}(C)\ .\\
\eaq\end{displaymath}
\indent Let $C={\it GH}$. By the induction hypothesis, there are models ${\it Pr}_1\in {\it Mo}(B,G)$ 
and ${\it Pr}_2\in {\it Mo}(B,H)$ with ${\it Pr}_1(B)>0$, ${\it Pr}_2(B)>0$, ${\it Pr}_1(L(G))>0$, ${\it Pr}_2(L(H))>0$, and
\begin{displaymath}\baq{ll} 
u_1\cdot {\it Pr}_1(B)={\it Pr}_1(BL(G)),\!  & x_1\cdot{\it Pr}_2(B)={\it Pr}_2(BL(H))\\
v_1\cdot {\it Pr}_1(L(G))={\it Pr}_1(BL(G)),\!  & y_1\cdot{\it Pr}_2(L(H))={\it Pr}_2(BL(H))\ .\\
\eaq\end{displaymath}
\indent By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(B)={\it Pr}_2(B)$
and ${\it Pr}_1(\ol{B}\,\ol{L(G)})\ge {\it Pr}_2(\ol{B}L(H)$.
By Lemmata~\ref{MAGIC} and \ref{magic1+}~b), we can choose the probabilistic interpretation ${\it Pr}_0$ over $\{B,L(G),L(H)\}$ with
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,L(G)\}$ 
and $\{B,L(H)\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(\ol{B}L(G)L(H))&=&\min({\it Pr}_2(\ol{B}L(H)),{\it Pr}_1(\ol{B}L(G)))&&\\[0.2ex]
{\it Pr}_0(BL(G)L(H))&=&\max(0,{\it Pr}_2(BL(H))-{\it Pr}_1(B\ol{L(G)}))\ .\!\!&&\\\eaq\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1={\cal B}(B,G)\setminus\{B\}$, ${\cal B}_2={\cal B}(B,H)\setminus\{B\}$, 
$B_0=B$, $B_1=L(G)$, and $B_2=L(H)$, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, 
it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
By Lemma~\ref{magic1+}~b), we get ${\it Pr}(L(C))>0$ and
\begin{displaymath}\baq{lcccccl}
\delta_1&\!\!=\!\!&1\,/\,(1+\frac{\min(u_1/v_1-u_1,\,x_1/y_1-x_1)}{u_1+x_1-1})& \!\!=\!\!
&1\,/\,(1+\frac{{\it Pr}(\ol{B}L(G)L(H))/{\it Pr}(B)}{{\it Pr}(BL(G)L(H))/{\it Pr}(B)}
)   &\!\!=\!\!&\frac{{\it Pr}(BL(C))}{{\it Pr}(L(C))}\vspace*{1.5ex}\\
\alpha_1&\!\!=\!\!&u_1+x_1-1& \!\!=\!\! 
&\frac{{\it Pr}(BL(G)L(H))}{{\it Pr}(B)}
&\!\!=\!\!&\frac{{\it Pr}(BL(C))}{{\it Pr}(B)}\ .\\
\eaq\end{displaymath}

\noindent c) Let $C={\it GH}$. By Theorem~\ref{LEM1}~b), there exist ${\it Pr}_1\in {\it Mo}(B,G)$ 
and ${\it Pr}_2\in {\it Mo}(B,H)$ with ${\it Pr}_1(B)>0$, ${\it Pr}_2(B)>0$,
$u_1\cdot {\it Pr}_1(B)={\it Pr}_1(BL(G))$, and $x_1\cdot{\it Pr}_2(B)={\it Pr}_2(BL(H))$.
By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ such that ${\it Pr}_1(B)={\it Pr}_2(B)$
and ${\it Pr}_1(\ol{B}\,\ol{L(G)})\ge {\it Pr}_2(\ol{B}L(H)$.
By Lemmata~\ref{MAGIC} and \ref{magic1+}~b), we can choose the probabilistic interpretation ${\it Pr}_0$ over $\{B,L(G),L(H)\}$ with
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,L(G)\}$ 
and $\{B,L(H)\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(\ol{B}L(G)L(H))&=&\max(0,{\it Pr}_2(\ol{B}L(H)-{\it Pr}_1(\ol{B}\,\ol{L(G)}))&=&0\\[0.2ex]
{\it Pr}_0(BL(G)L(H))&=&\max(0,{\it Pr}_2(BL(H))-{\it Pr}_1(B\ol{L(G)}))\ .\!\!&&\\\eaq\end{displaymath} 
\indent By Lemma~\ref{COMMM} with ${\cal B}_1={\cal B}(B,G)\setminus\{B\}$, ${\cal B}_2={\cal B}(B,H)\setminus\{B\}$, 
$B_0=B$, $B_1=L(G)$, and $B_2=L(H)$, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, 
it holds ${\it Pr}\in{\it Mo}(B,C)$ and ${\it Pr}(B)>0$.
By Lemma~\ref{magic1+}~b), we get ${\it Pr}(L(C))>0$ and
\begin{displaymath}\baq{lllll}
  1 &=&{\it Pr}(BL(G)L(H))\,/\,{\it Pr}(L(G)L(H)) &=&{\it Pr}(BL(C))\,/\,{\it Pr}(L(C))\\[1ex]
\alpha_1  &=&{\it Pr}(BL(G)L(H))\,/\,{\it Pr}(B)) &=&{\it Pr}(BL(C))\,/\,{\it Pr}(B)\ .\\
\eaq\end{displaymath}

\noindent d) Let $C={\it GH}$. By Theorem~\ref{Doll}, there is a model $\Pr'''\in{\it Mo}(B,C)$ with $\Pr'''(BL(C))>0$. 
By Theorem~\ref{LEM1}~b), there is a model  $\Pr''$$\,\in$$\,{\it Mo}(B,C)$ with $\Pr''(B)$$\,>$$\,0$ and 
$0\cdot\Pr''(B)=\alpha_1\cdot\Pr''(B)=\Pr''(BL(C))$. 
Hence, there is a model  $\Pr'\in{\it Mo}(B,C)$ with $\Pr'(B)>0$ and 
\begin{displaymath}
\mbox{$\min(\varepsilon,\Pr'''(BL(C))\,/\,\Pr'''(B))\cdot \Pr'(B)=\Pr'(BL(C))\ .$}
\end{displaymath}
Let the models $\Pr_1\in{\it Mo}(B,G)$ and $\Pr_2\in{\it Mo}(B,H)$ be defined 
by $\Pr_1(A_1)=\Pr'(A_1)$ and $\Pr_2(A_2)=\Pr'(A_2)$ for all atomic events $A_1$ and 
$A_2$ over ${\cal B}(B,G)$ and ${\cal B}(B,H)$, respectively.
By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ such that ${\it Pr}_1(B)={\it Pr}_2(B)$
and ${\it Pr}_1(\ol{B}\,\ol{L(G)})\ge {\it Pr}_2(\ol{B}L(H)$.
By Lemmata~\ref{MAGIC} and \ref{magic1+}~b), we can choose the probabilistic interpretation ${\it Pr}_0$ over $\{B,L(G),L(H)\}$ with
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ for all atomic events $A_1$ and $A_2$ over $\{B,L(G)\}$ 
and $\{B,L(H)\}$, respectively, such that:
\begin{displaymath}\baq{lllll}{\it Pr}_0(\ol{B}L(G)L(H))&=&\max(0,{\it Pr}_2(\ol{B}L(H)-{\it Pr}_1(\ol{B}\,\ol{L(G)}))&=&0\\[0.2ex]
{\it Pr}_0(BL(G)L(H))&=&\min(\varepsilon,\Pr'''(BL(C))\,/\,\Pr'''(B))\cdot {\it Pr}_0(B)\ .\!\!&&\\\eaq\end{displaymath} 
By Lemma~\ref{COMMM} with ${\cal B}_1={\cal B}(B,G)\setminus\{B\}$, ${\cal B}_2={\cal B}(B,H)\setminus\{B\}$, 
$B_0=B$, $B_1=L(G)$, and $B_2=L(H)$, there is a probabilistic interpretation
${\it Pr}$ over ${\cal B}(B,C)$ with (\ref{XCOMMM}). Hence, it holds ${\it Pr}$$\,\in$$\,{\it Mo}(B,C)$,
${\it Pr}(B)$$\,>$$\,0$, ${\it Pr}(L(C))$$\,>$$\,0$, 
${\it Pr}(\ol{B}L(C))$$\,=$$\,0$, and $\varepsilon\cdot{\it Pr}(B)$$\,\ge $$\,{\it Pr}({\it BL(C)})$. $\Box$

\bigskip
\noindent{\bf Proof of Theorem~\ref{Theorem48}.}
For $u_1>0$, the claim is immediate by Theorem~\ref{NEUT}~a) to c).

Let $u_1=0$ and $E\Rightarrow F$. It holds $1\cdot\Pr(E)=\Pr({\it EF})$ for all models $\Pr$ of ${\it KB}$. 
Moreover, by Theorem~\ref{Doll}, there exists a model $\Pr$ of ${\it KB}$ with $\Pr(E)>0$.

Let $u_1=0$ and not $E\Rightarrow F$. By Theorem~\ref{LEM1}~b), there exists a model $\Pr$ of ${\it KB}$
with $\Pr(E)$$\,>$$\,0$ and $\Pr({\it EF})$$\,=$$\,0$. By Theorem~\ref{NEUT}~d), there exists a model 
$\Pr$ of ${\it KB}$ with $\Pr(E)$$\,>$$\,0$ and $1\cdot\Pr(E)=\Pr({\it EF})$. $\Box$


\section*{Appendix D. Proofs for Section~\ref{QUERYY}}
\setcounter{section}{4}\label{appd}
In this section, we give the proof of Theorem \ref{Theorem49}.

The next lemma will help us to show the global tightness
of the computed lower bound in the case (3) of Theorem~\ref{Theorem49}~b).  
%
\ble \label{magic1++}
Let $x\in[0,1]$ and $\ol{v},\ol{x}\in[0,\infty)$. 
For all probabilistic interpretations ${\it Pr}$ with ${\it Pr}({\it G})>0$,
the conditions ${\it Pr}({\it E G})=0$, $\ol{v}\cdot{\it Pr}(G)={\it Pr}({\it E\ol{G}})$, 
$x\cdot{\it Pr}(G)={\it Pr}({\it GF })$,
and $\ol{x}\cdot{\it Pr}(G)={\it Pr}({\it \ol{G}F })$ are equivalent to:

\bigskip
\noindent\phantom{.}\hfill$\baq{cc|c}\frac{{\it Pr}(\ol{E}\,\ol{G}\,\ol{F} )}{{\it Pr}(G)}&\ \frac{{\it Pr}(\ol{E}\,\ol{G}F )}{{\it Pr}(G)}\ &\  \frac{{\it Pr}(\ol{E}\,\ol{G})}{{\it Pr}(G)}\\[1.3ex] 
                   \frac{{\it Pr}(E \ol{G}\,\ol{F} )}{{\it Pr}(G )}&\frac{{\it Pr}({\it E \ol{G}F })}{{\it Pr}(G )}& \ol{v}\\[1.5ex]\hline
                   &&\\[-3ex]
                    \frac{{\it Pr}(\ol{G}\,\ol{F} )}{{\it Pr}(G)} &\ol{x}& \\\eaq$ \hfill
$\baq{cc|c}\frac{{\it Pr}(\ol{E} G\ol{F} )}{{\it Pr}(G )}&\ \frac{{\it Pr}(\ol{E} {\it GF })}{{\it Pr}(G )}\ & 1\\[1.3ex]
                   \frac{{\it Pr}({\it E G}\ol{F} )}{{\it Pr}(G )}&\frac{{\it Pr}({\it E GF })}{{\it Pr}(G )}& 0\\[1.5ex]\hline 
                   &&\\[-3ex]
                    1-x & x & \eaq$\hfill\phantom{.}
\ele

\medskip
\noindent{\bf Proof.} The claim can be verified by straightforward arithmetic transformations
based on the properties of probabilistic interpretations. $\Box$

\medskip
We are now ready to prove Theorem~\ref{Theorem49}.

\medskip
\noindent{\bf Proof of Theorem~\ref{Theorem49}.} a) By the definition of queries to conditional constraint trees, 
all paths from a basic event in $E$ to a basic event in $F$ have at least one basic event in common. 
Hence, we can choose the basic event $G$ from all such basic events in common such that 
$\exists\urule{E}{z_1,z_2}{G}$ is a strongly con\-clu\-sion-re\-strict\-ed complete query
to a subtree. 

\medskip
\noindent b) For $u_1>0$, the claim follows from Theorem~\ref{NEUT}~a) to c). For the special case
of exact conditional constraint trees $({\cal B},{\it KB})$, the claim then follows
from Theorems~\ref{LEM1} and $\ref{HALLO1}$.

Let $u_1=0$, $v_1=1$, and $G\Rightarrow F$. It holds $1\cdot\Pr(E)=\Pr({\it EF})$ for all 
models $\Pr$ of ${\it KB}$. Moreover, by Theorem~\ref{Doll}, 
there exists a model $\Pr$ of ${\it KB}$ with $\Pr(E)>0$.

Let $u_1=0$, $v_1=0$, and $G\Rightarrow F$. It is easy to see that by (1) and 
Theorem~\ref{NEUT}~d), the tight upper answer is given by $\{x_2/1\}$.
We now show that the tight lower answer is given by $\{x_1/0\}$. 
By Theorem~\ref{LEM1} b), there exists a model  $\Pr_1$ of ${\it KB}_1$ with \mbox{$\Pr_1(E)>0$}, 
$\Pr_1(G)>0$, and $\Pr_1({\it EG})=0$. By Theorem~\ref{Doll}, there exists 
a model $\Pr_2$ of ${\it KB}_2$ with $\Pr_2(G)>0$. 
By Lemma~\ref{Toll}, we can choose  ${\it Pr}_1$ and ${\it Pr}_2$ with ${\it Pr}_1(G)={\it Pr}_2(G)$
and ${\it Pr}_1(\ol{E}\,\ol{G})\ge {\it Pr}_2(\ol{G}F)$.
By Lemmata~\ref{MAGIC} and \ref{magic1++}, we can choose the probabilistic interpretation 
${\it Pr}_0$ over $\{E,G,F\}$ with
${\it Pr}_0(A_1)={\it Pr}_1(A_1)$ and ${\it Pr}_0(A_2)={\it Pr}_2(A_2)$ 
for all atomic events $A_1$ and $A_2$ over $\{E,G\}$ 
and $\{G,F\}$, respectively, such that:
\begin{displaymath}\baq{lllll}
{\it Pr}_0(E\ol{G}F)&=&\max(0,{\it Pr}_2(\ol{G}F)-{\it Pr}_1(\ol{E}\,\ol{G}))&=&0\\[0.2ex]
{\it Pr}_0({\it EGF})&=&0\ .&&\\\eaq\end{displaymath} 
By Lemma~\ref{COMMM}, there exists a probabilistic interpretation
${\it Pr}$ over ${\cal B}$ with (\ref{XCOMMM}) 
for all atomic events $H_0$, $H_1$, $H_2$, $A_1$, and $A_2$ over the sets of basic 
events $\{G\}$, $\{E\}$, $\{F\}$, ${\cal B}_1\setminus \{G\}$, and 
${\cal B}_2\setminus \{G\}$, respectively. Hence, $\Pr$ is 
a model of ${\it KB}$ with $\Pr(E)>0$ and $\Pr({\it EF})=0$.

For $u_1=0$ and not $G\Rightarrow F$, the claim follows from (1) and Theorem~\ref{NEUT}~d). $\Box$

\nocite{Luk96}
\nocite{Luk97}
\nocite{Luk98a}
\nocite{Luk98b}
\nocite{Luk98c}
\nocite{Luk98d}
\nocite{Luk99b}
\nocite{Luk99c}
\nocite{Ada75}
\nocite{Carnap50}
\nocite{deF74}
\nocite{Walley91}
\nocite{Nil93}
\nocite{DP88} 
\nocite{DPT90}
\nocite{ADP91a}
\nocite{DPGM93}
\nocite{FH94}
\nocite{Tho94}
\nocite{TKG95}
\nocite{Hein94} 
\nocite{GeoKP88}
\nocite{KP90}
\nocite{jahapo91}
\nocite{AH94}
\nocite{HJNA95}
\nocite{LYLWP96}
\nocite{FHM92}
\nocite{Nil86}
\nocite{paass88} 
\nocite{G42}
\nocite{Bac90}
\nocite{Hal90}
%\nocite{AbHa94}
\nocite{BGHK96}
\nocite{NS93}
%\nocite{Ng1997}
\nocite{NgSub94} 
\nocite{Pea88}
\nocite{Gaag91}
\nocite{Pap82}  
\nocite{Schr86}
\nocite{Col94} 
\nocite{GS94}
\nocite{Pittarelli94}

\vskip 0.2in
\bibliographystyle{theapa}
\bibliography{jair577}

\end{document}


