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

\jairheading{3}{1995}{349-372}{5/95}{12/95}
\ShortHeadings{Horn Expressions and Characteristic Models}
{Khardon}
\firstpageno{349}

\begin{document}

\title{
      Translating between Horn Representations  \\ 
      and their Characteristic Models
      }



\author{
       \name Roni Khardon \email roni@das.harvard.edu \\
       \addr  Aiken Computation Lab., Harvard University \\
	Cambridge, MA 02138 USA 
       }


\maketitle


\input{style.tex}


\input{psfig}
\setcounter{figure}{0}

\date{February, 1995 \\ (Revised \today)}

\maketitle

{\small
\begin{abstract}
Characteristic models
are an alternative, model based, representation for Horn expressions.
It has been shown that these two representations are incomparable and
each has its advantages over the other.
It is therefore natural to ask what is the cost of translating, back
and forth, between these representations.
Interestingly, 
the same translation questions arise in database theory, 
where it has applications to the design of  relational databases.
This paper studies the computational complexity of these problems.

Our main result is that the two translation problems 
are equivalent under polynomial reductions, and that they are equivalent to
the corresponding decision problem.
Namely, translating is equivalent to deciding whether a given set of 
models is the set of characteristic models for a given Horn expression.

We also relate
these problems to the hypergraph transversal problem,
a well known problem which is related to other applications in AI
and for which no polynomial 
time algorithm is known.
It is shown that
in general our translation problems are at least as hard as the 
hypergraph transversal problem, and
in a special case they are equivalent to it.

\end{abstract}
}


\section{Introduction}

The traditional form of representing knowledge in AI is through logical
formulas \cite{McCarthy58,McCarthyHa69}, where all the logical conclusions
of a given
formula are assumed to be accessible to an agent. 
Recently, an alternative way of capturing such information has been
developed \cite{KautzKeSe95,KhardonRo94a}. 
Instead of using a logical formula, the knowledge representation is
composed of a particular subset of its models, 
the set of {\em characteristic models}.
This set retains all the information about the formula,
and is useful for various reasoning tasks.
In particular, 
using model evaluation with the set of characteristic models,
one can deduce whether another
formula, a query presented to an agent, is implied by the knowledge 
or not. 
While characteristic models exist for arbitrary propositional formulas,
in this paper we limit our attention to  logical formulas which are in 
Horn form
and to their representation as characteristic models.


The characteristic models of Horn formulas have been shown to be useful.
There is a linear time deduction algorithm using this set, and abduction
can be performed in polynomial time, while using formulas it is NP-Hard
\cite{KautzKeSe95}.  
Furthermore, an algorithm for default reasoning using characteristic models
has been developed, for cases where formula based algorithms are not known
\cite{KhardonRo95def}.
Hence, 
the question arises, whether one can
efficiently translate a Horn formula into its set of characteristic models 
and then use this set for the reasoning task.
We denote this translation problem by CCM (for Computing Characteristic
Models).

On the other hand, given a set of assignments, 
it might be desirable to find the underlying structure behind this 
set of models.
This is the case when one is trying to learn the structure of the world
using a set of examples.
This problem has been studied before under the name Structure Identification
\cite{DechterPe92,KautzKeSe95,KavvadiasPaSi93}.
Technically, the problem
seeks an efficient translation from
a set of characteristic models into a Horn expression that explains it.
We denote this translation problem by SID (for Structure Identification).

Interestingly, the same constructs appear in the theory of 
relational databases.
As shown in a companion paper \cite{KhardonMaRo95},
there is a correspondence between Horn expressions and Functional
Dependencies, and a correspondence between characteristic models and
an Armstrong relation. 
The equivalent question of translating  between
functional dependencies and Armstrong relations 
has been studied before 
\cite{BeeriDoFaSt84,MannilaRa86,EiterGo91,GottlobLi90}
and is relevant for the design of relational
databases \cite{MannilaRa86}.
While this paper does not discuss the problems in the database domain,
some of the results presented here can be alternatively derived from 
previous results in database theory using the above mentioned equivalence. 
(We identify those precisely, later on.)
However, this paper makes these results more accessible without resorting to
any results in database theory, and with simpler proofs.
On the other hand some new results are presented, 
which resolve a question which was open both in AI and in the database domain.

\subsection{An Example}

Let us introduce the 
problems in question
through an example. Suppose the world
has 4 attributes denoted $a,b,c,d$, each taking a value in
$\zerone$ to denote whether it is ``on" or ``off", and our knowledge is 
given by the following constraints:
\[ W = (bc\ra d)(cd\ra b)(bc\ra a). \]
Then $W$ is a Horn expression and it is normally used to decide whether
certain constrains are implied by it or not.
For example $W\models (cd\ra a)$,  and $W\not\models (bd\ra a)$,
where the symbol $\models$ stands for implication. 
This is normally performed by deriving a proof for the constraint in 
question. If no such proof exists then implication does not hold.
In our example we would notice that $(cd\ra b)$, 
and therefore $(cd\ra bc\ra a)$. 
As for $(bd\ra a)$, we would fail to find a proof and therefore 
conclude that it is not implied by $W$.
This general approach is called theorem proving, and is efficient for
Horn expressions \cite{DowlingGa84}.

An alternative approach is to check the implication relation by model
checking. Implication is defined as follows: $W\models \alpha$ if every
model of $W$ is also a model of $\alpha$ (where $x\in \cuben$ is a model of 
an expression $f$ if $f$ is evaluated to ``truth" on $x$).
So to decide whether $W\models \alpha$ 
we can simply use all the models of $W$, and check, one by one,
whether any of them does not satisfy $\alpha$.
In our example $W$ has 11 models:
\[ models(W)= \{ 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010,
		 1100, 1101, 1111 \}  \]
(where the assignments denote the values assigned to $abcd$
correspondingly), and we would have to test $\alpha$ on every one of them.
Unfortunately, in general the number of models may be very large,
exponential in the number of variables, and therefore this procedure will
not be efficient.

The question arises therefore, whether there is a small subset of 
models which still guarantees correct results when used with the 
model checking procedure.
Such a subset is called the set of {\em characteristic models} of $W$
and its existence has been proved \cite{KautzKeSe95,KhardonRo94a}.
In our example this set is:
\[ char(W)=\{ 0010, 0101, 1001, 1010, 1100, 1101, 1111  \}, \]
so it includes 7 out of the 11 models of $W$.
Model checking with this set is guaranteed to produce correct results for
any $\alpha$ which is a Horn expression, and using a slightly more
complicated algorithm one can answer correctly for every $\alpha$
\cite{KautzKeSe95}.
In our example, it
is easy to check that $(cd\ra a)$ is evaluated to ``truth" on all the
assignments in $char(W)$ and that $(bd\ra a)$ is falsified by $0101$.

The utility of these representations, Horn expressions and characteristic
models, is not comparable.
Each of these representations has its advantages over the other. 
First, the size of these representations is incomparable.
There are short Horn expressions for which the set of characteristic
models is of exponential size, and vice versa, there are also exponential
size Horn
expressions for which the set of characteristic models is small
\cite{KautzKeSe95}.
The representations also differ in the services which they support.
On one hand,
Horn expressions are more comprehensible. On the other hand
characteristic
models are advantageous in that they allow  for efficient algorithms 
for abduction and default reasoning. 
In this paper we are asking how hard it is to translate
between these representations, so as to enjoy the benefits of both.

\subsection{Overview of the Paper}

In this paper we study the complexity of the translation problems
CCM and SID.
%
For these problems, the output may be exponentially larger than the input.
Therefore, 
it is appropriate to ask whether there are algorithms which can perform the
above tasks in time which is polynomial in both the input size and the
output size. These are called output polynomial algorithms.

Before starting our investigation we note that
it has been shown \cite{KautzKeSe95} that using the set of 
characteristic models one can answer abduction queries related to $H$
in polynomial time,
while given the formula $H$ it is NP-Hard to perform abduction 
\cite{SelmanLe90}.
This however does not imply
that computing the set of characteristic models
is NP-Hard since the construction in the proof yields a Horn formula
whose set of characteristic models is of exponential size.



Our main result says that CCM and SID are equivalent to each other, and are 
also equivalent to the corresponding decision problem.
The problem of Characteristic Models Identification (CMI), is the problem
of deciding, given a Horn expression $H$ and a set of models $G$,
whether $G=char(H)$.
We show that CCM, SID, and CMI are equivalent under polynomial reductions.
Namely, the translation problems are solvable in polynomial time
if and only if the decision problem is solvable in polynomial time.
These are new results which have immediate corollaries in the database domain.



We then show a close relationship between these problems and the
Hypergraph Transversal Problem (HTR). 
Given a hypergraph $G$ a transversal of its edges is a set of nodes
which touches every edge in the graph.
In the HTR problem one is given 
a hypergraph as an input, and is required to compute the set 
of minimal transversals of its edges.

The HTR problem has a lot of equivalent manifestations
which appear in various branches of computer science.
Examples in AI include computing abductive diagnoses \cite{Reiter87b},
enumerating prime implicants in ATMS \cite{ReiterDeKl87},
and Horn approximations \cite{KavvadiasPaSi93} which are closely 
related to characteristic models.
Other areas include database theory \cite{MannilaRa86}, 
Boolean complexity, and distributed systems \cite{EiterGo91}.
A comprehensive study of these
problems is presented by Eiter and Gottlob \citeyear{EiterGo94}.
%
HTR is also equivalent to the problem of dualization of monotone Boolean 
expressions, which is the form in which we present it here. 
This problem, requires
translation between the CNF and DNF representations of 
monotone functions. 

The complexity of the HTR problem has been studied before 
\cite{FredmanKh94,EiterGo94,KavvadiasPaSi93} and is still   
an open question. 
On one hand a class of problems which are ``HTR
complete" has been defined and studied \cite{EiterGo94}.
This class includes many problems from various application areas
which are equivalent to HTR (under polynomial reductions).
On the other hand the problem is probably not NP-Complete.
Recently, Fredman and Khachiyan \citeyear{FredmanKh94} have presented a
sub-exponential $n^{O(\log n)}$
time algorithm for the HTR problem.


We first show that the problem CCM is at least as hard as HTR.  
By that we mean that if there is an output polynomial algorithm for CCM
then there is an output polynomial algorithm for HTR.
This has been stated as an open problem by Kavvadias et. al.
\citeyear{KavvadiasPaSi93}, who proved a 
similar hardness result for SID.
Both hardness results can be alternatively derived by combining 
previous results in database theory
\cite{EiterGo94,BiochIb93} and its relation to our problems
\cite{KhardonMaRo95}.

We then consider two relaxations of these translation problems.
The first is considering redundant Horn expressions which contain
{\em all} the Horn prime implicates for a given expression.
The output of SID is therefore altered to be the set of all prime 
implicates, and similarly the input of CCM includes all the prime
implicates instead of a minimal subset.
It is shown that in 
this special case, SID, CCM, and HTR are equivalent under polynomial
reductions.
Therefore, the algorithm presented by Fredman and Khachiyan
\citeyear{FredmanKh94} can be used to solve CCM, and SID in time
$n^{O(\log n)}$. 
This result can be alternatively derived from
the results on functional dependencies in MAK form \cite{EiterGo91}.
We show however that our argument generalizes to the larger family of 
$k$-quasi Horn expressions.

The second relaxation is
the problem of computing all the prime implicants for a given Horn
expression. This is a relaxation of CCM since 
using the prime implicants one can compute the characteristic models.
Interestingly,
the algorithm for HTR \cite{FredmanKh94} can be adapted to this
problem, resulting an algorithm with time complexity $n^{O(\log^2 n)}$.

It is shown, however, that both relaxations do not help in solving the
general cases of CCM and SID due to exponential gaps in the size of the 
corresponding representations.

Lastly, we consider a
related problem, denoted EOC, which is a minor modification
of CCM and SID. 
This problem is shown to be co-NP-Complete. 
This serves to highlight some of the difficulty in finding the 
exact complexity of our problems.
A variant of this result, has already
appeared in the database literature \cite{GottlobLi90}.


\begin{figure}[tb]
\label{fig:sum}
\centerline{\mbox{\psfig{figure=sum.ps}}}
\caption{Summary of Complexity Results}
\end{figure}

Our results are summarized in Figure~1, where a hierarchy of problems is depicted.
The problem EOC is co-NP-Complete. The problem CMI is a special case of EOC, and is
equivalent to SID and CCM.
The problem HTR is a special case of CMI and is equivalent to SID and CCM under the 
restriction that the Horn expression is represented by the set of all prime implicates.

The rest of the paper is organized as follows. Section~2 
defines characteristic models, describes some of their 
properties, and formally defines the problems in question.
Section~3 discusses the relation between CCM,SID and the corresponding
decision problem.
Section~4 discusses the relation to the HTR problem. 
We first establish the hardness result, and then consider the 
two relaxations mentioned above.
Section~5 shows that EOC is co-NP-Hard, and
Section~6 concludes with a summary.

\section{Preliminaries}
\label{sec:prel}

This section includes the basic definitions, and introduces several previous
results which are used in the paper.

We consider Boolean functions $f:\cuben\rightarrow\zerone$.
The elements in the set $\{x_1,\ldots,x_n\}$ are called variables.
Assignments in $\{0,1\}^{n}$ are denoted by $x,y,z$, and 
$weight(x)$ denotes the number of 1 bits in the assignment $x$.
A literal is either a variable $x_i$ 
(called a positive literal) or its negation $\overline{x_i}$
(a negative literal).
A clause is a disjunction of literals, and a CNF formula is a conjunction
of clauses. 
For example $(\xa \vee \nxb)\wedge (\xc\vee \nxa\vee\xd )$
is a CNF formula with two clauses.
A term is a conjunction of literals, and a DNF formula is a
disjunction of terms.
For example $(\xa \wedge \nxb)\vee (\xc\wedge \nxa\wedge\xd)$
is a DNF formula with two terms.
A CNF formula is Horn if every clause in it has at most one positive
literal.
A formula is monotone if all the literals that appear in it are positive.
The size of CNF and DNF representations is, respectively, 
the number of clauses and the number of terms in the representation.
We denote by $|DNF(f)|$ the size of the smallest DNF representation for $f$.

An assignment $x\in \cuben$ satisfies $f$ if $f(x)=1$. Such an assignment
$x$ is also called a model of $f$.
By ``$f$ implies $g$", denoted $f\models g$, we mean that every model
of $f$ is also a model of $g$. 
Throughout the paper, when no confusion can arise, we identify 
a Boolean function $f$ with 
the set of its models, namely $f^{-1}(1)$.
Observe that the connective ``implies'' ($\models$) used between Boolean 
functions is equivalent to the connective ``subset or equal''
($\subseteq$) used for subsets of $\{0,1\}^{n}$. That is,
$f\models g$ if and only if $f\subseteq g$.

A term $t$ is an {\em implicant} of a function $f$, if $t\models f$.
A term $t$ is a {\em prime implicant} of a function $f$, if 
$t$ is an implicant of $f$ and 
the conjunction of any proper subset of the literals in $t$ 
is not an implicant of $f$.

A clause $d$ is an {\em implicate} of a function $f$, if $f \models d$.
A clause $d$ is a {\em prime implicate} of a function $f$, if $d$ is an
implicate of $f$ and the disjunction of any proper subset of the literals
in $d$ is not an implicate of $f$.

It is well known that,
a minimal DNF representation of $f$ is a disjunction of some of its prime
implicants.
A minimal CNF representation of $f$ is a conjunction of some of its prime
implicates.

If $f$ is monotone, then it has a unique minimal DNF representation
(using all the prime implicants), and a unique minimal CNF representation 
(using all its prime implicates).

\subsection{Characteristic Models}

The idea of using 
characteristic models as a knowledge representation was 
introduced by Kautz et. al.  \citeyear{KautzKeSe95}.
Characteristic models were 
studied in AI \cite{DechterPe92,KavvadiasPaSi93,KhardonRo94a} and
under a different manifestation in database theory
\cite{BeeriDoFaSt84,MannilaRa86,GottlobLi90,EiterGo91,EiterGo94}.
This section defines characteristic models and their basic properties.

For $u,v\in\cuben$, we define the {\em intersection} of $u$ and $v$ to
be the assignment $z \in \{0,1\}^{n}$ such that
$z_i = 1$ if and only if $u_i=1$ and $v_i=1$ (i.e., the
bitwise logical-and of $u$ and $v$.).

For a set of assignments $S$, $x=intersect(S)$
is the assignment we get by intersecting all the assignments in $S$.
We say that $S$ is {\em redundant}
if there exists $x\in S$ and $S'\subseteq S$ such that 
$x\not\in S'$ and 
$x=intersect(S')$. Otherwise $S$ is {\em non-redundant}.

The {\em closure} of $S\subseteq \cuben$, denoted $closure(S)$,
is defined as the
smallest set containing $S$ that is closed under intersection.

To illustrate these definitions consider the set
$M=\{1101,1110,0101\}$. Then $M$ is non-redundant,
$intersect(M)=0100$, and $closure(M)=\{1101, 1110, 0101, 0100, 1100\}$.

Let $H$ be a Horn expression.
The set of the {\em Horn characteristic models} of $H$, denoted here
$char(H)$ is defined as the set of models
of $H$ that are not the intersection of other models of $H$. 
Note that $char(H)$ is non-redundant.
Formally,
\begin{equation}
\label{eq:charh}
char(H)=\{u\in H \ |\ u\not\in closure(H\setminus\{u\})\ \} .
\end{equation}
For example, $char(\{1101,1110,0101,0100\})=\{1101,1110,0101\}$.

It is well known that
the set of models of Horn expressions is closed under intersection.
This result is due to McKinsey \citeyear{McKinsey43}, who proved
it for a certain class of first order sentences. Alfred Horn
\citeyear{Horn51} considered a more general class of
sentences. (Lemma~7 by Horn \citeyear{Horn51} deals with the propositional case.
Dechter and Pearl \citeyear{DechterPe92} present 
another proof for the propositional
case.) Moreover, since characteristic models capture all the information
about the closure, they also capture all the information about the Horn
expression.

\begin{theorem}{\bf \cite{KautzKeSe95,DechterPe92}}
\label{thm:kks}
Let $H$ be a Horn expression then $H=closure(char(H))$.
\end{theorem}

\subsection{Monotone Theory and Characteristic Models}

The monotone theory was introduced by Bshouty \citeyear{Bshouty93}, and was
later
used for a theory for model-based reasoning \cite{KhardonRo94a}.
This section explores the relations between the monotone theory and characteristic models.

\begin{definition}[Order]
We denote by $\leq$ the {\em usual partial order} on the lattice $\{0,1\}^{n}$,
the one induced by the order $0<1$. That
is, for $x,y \in \{0,1\}^{n}$,
$x \leq y$ if and only if $\forall i, x_i \leq y_i$.
For an assignment $b \in \{0,1\}^{n}$ we define 
$x \leq_{b} y$ if and only if $x\oplus b \leq y\oplus b$ 
(Here $\oplus$ is the bitwise addition modulo $2$).
We say that $x> y$ if and only if $x\geq y$ and $x\not = y$.
\end{definition}

Intuitively, if $b_i=0$ then the order relation on the $i$th bit is the
normal order; if $b_i=1$, the order relation is reversed and we
have that $1 <_{b_i} 0$. For example $0101 <_{1111} 0100$, and
$0101 \not <_{1111} 0110$.
We now define: \\
The {\em monotone extension of $z \in \{0,1\}^{n}$} with respect to $b$:
$$\mon_b(z)=\{x\ |\ x\geqb z\}.$$
The {\em monotone extension of $f$} with respect to $b$:
$$\mon_b(f)=\{x\ |\ x\geqb z, {\mbox \ for\ some\ } z \in f\}.$$
The set of {\em minimal assignments of $f$} with respect to $b$:
$$\min_b(f)=\{z\ |\ z\in f,\ {\mbox \ such\ that\ } 
\forall y\in f, z \not>_b y \}. $$
%
For example $$\mon_{1111}(0101)=\{0101,0001,0100,0000\}, \ \ \ \mbox{and}$$  
$$\mon_{1111}(1100)=\{1100,0100,1000,0000\}.$$ 
Let $f=b \ov{c} (\ov{a} \vee \ov{d})(a \vee d)$, then in the set notation
$f=\{1100,0101\}$, and $\mon_{1111}(f)=\{0101,0001,0100,0000,1100,1000\}$.
The set $\min_{1111}(f)=\{1100,0101\}$, 
and  the set \\ $\min_{0001}(f)=\{0101\}$.


Clearly, for every assignment $b\in \{0,1\}^{n}$, $f\subseteq \mon_b(f)$.
Moreover, if $b\not\in f$, then $b\not\in\mon_b(f)$ (since $b$ is 
the smallest assignment with respect to the order $\leq_b$).
Therefore:
$$f=\And_{b\in\cuben}\mon_b(f) = \And_{b\not \in f}\mon_b(f).$$
The question is if we can
find a small set of negative examples, and use it to represent
$f$ as above.

\begin{definition}[Basis]
A set $B$ is a {\em basis for $f$} if $f=\And_{b\in B}\mon_b(f)$.
$B$ is a basis for a class of functions ${\cal F}$  
if it is a basis for all the functions in ${\cal F}$.
\end{definition}

\pp
Using this definition, we get an alternative representation for functions
\begin{equation}
\label{eq:monotone}
f=\And_{b\in B}\mon_b(f)= \And_{b\in B} \Or_{z\in \min_b(f)} \mon_b(z).
\end{equation}

\pp
It is known that
the set $B_H=\{u\in\cuben\ |\ \mbox{ weight}(u) \geq n-1\}$,
is a basis for any Horn CNF function. 
For example consider the Horn expression 
$ W = (bc\ra d)(cd\ra b)(bc\ra a)$ discussed in the introduction.
Recall that the satisfying assignments of $W$ are:
\[ models(W)= \{ 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010,
		 1100, 1101, 1111 \}.  \]
We have to compute the sets $\min_b(W)$ for $b\in B_H$,
where $B_H=\{1111,1110,1101,1011,0111\}$.
Note that if $b$ satisfies $f$ then $\min_b(f)=\{b\}$, and
$\mon_b(f)\equiv 1$ (that is, $\forall x$, $\mon_b(f)(x)=1$). 
Therefore, $\min_{1111}(W)=\{1111\}$, and $\min_{1101}(W)=\{1101\}$.
One way to compute the sets of minimal assignments
is by drawing the corresponding lattices and noting the relations there.
Figure~2 shows the lattice with respect to $b=0111$.
The satisfying assignments of $W$ are marked in bold face.
The minimal assignments are underlined, and some of the order relations,
which show that the rest of the assignments are not minimal, are drawn.
To compute $\mon_b(W)$ we have to add any assignment which is above the
minimal assignments. This is marked by the dotted lines which show that
$1011$ and $1110$ are in $\mon_{0111}(W)$.
Using the figure we observe that
$\min_{0111}(W)=\{1111,0101,0010\}$.
The other sets are $\min_{1110}(W)=\{1111,1100,1010\}$,
and $\min_{1011}(W)=\{1111,1001,1010\}$.


\begin{figure}[tb]
\label{fig:lattice}
\centerline{\mbox{\psfig{figure=lattice.ps}}}
\caption{Computing $\min_b(f)$ and $\mon_b(f)$}
\end{figure}


It is known that the size of the basis for a function $f$ 
is bounded by the size of its CNF representation, and that
for every $b$ the size of $\min_b(f)$ is bounded by the size
of its DNF representation.

For any function $f$ and set of assignments $B$ let:
$$\Gamma^{B}_{f}= \min_{B}(f) = \cup_{b\in B} \{ z\in \min_b(f)\}.$$
The following theorem gives an alternative way to define $char(H)$.

\begin{theorem}{\bf \cite{KhardonRo94a}}
\label{thm:same}
Let H be a Horn expression. Then 
$char(H)= \Gamma^{B_H}_{H}$.
\end{theorem}

Continuing the above example with the function 
$ W = (bc\ra d)(cd\ra b)(bc\ra a)$, we conclude that
$char(W)=\{0010, 0101, 1001, 1010, 1100, 1101, 1111 \}$.
As the following theorem shows
the set of characteristic models can be used to answer deduction queries.

\begin{theorem}{\bf \cite{KautzKeSe95,KhardonRo94a}}
\label{thm:deduct}
Let $H_1$, $H_2$ be Horn expressions then $H_1\models H_2$ if and only if
for all $x\in char(H_1)$, $H_2(x)=1$.
\end{theorem}

It is useful to have the DNF representation of a function.
If $f$ is given in its DNF representation then it is
easy to compute the set $min_b(f)$, for any $b$.
Each term in the DNF representation can contribute {\em at most} 
one assignment, $\min_b(t)$,
where the variables that appear in the term are fixed and the others are set
to their minimal value. 
This is true since from every other satisfying assignment of the term
we can ``walk down the lattice" towards this assignment, on a path composed
of satisfying assignments.
For example, the minimal assignment for the term $t=x_1 \nxc$,
with respect to the basis element $b=0011$, is $\min_{0011}(t)=\{1001\}$. 
The assignment $1100$ which also satisfies $t$
is not minimal since $1001<_{0011} 1101 <_{0011} 1100$.
Further, once we have one assignment from each term,
it is easy make sure that the set is non-redundant by checking which of the
assignments generated is in the intersection of the others.
We would use this algorithm later in some of our reductions.


We say that a
function is $b$-monotone if it is monotone according to the order
relation $\leq_b$. 
Namely, if whenever $f(x)=1$ and $y\geq_{b}x$ then $f(y)=1$.
%Notice that if we flip the polarity of the variables for which $b_i=1$
%(i.e. where the order relation is reversed) then $f$ becomes monotone.
Notice that if we rename the variable $x_i$ by its negation,
for each $i$ such that $b_i=1$
(i.e. where the order relation is reversed), then $f$ becomes monotone.
Therefore, $b$-monotone functions enjoy similar properties. 
For example,
they have unique minimal DNF and CNF representations.
Another property is that the  minimal assignment which corresponds to
every term is
indeed part of the set $\min_b(f)$.

\begin{claim}{\bf \cite{KhardonRo94a}}
\label{cl:size}
For any $b$-monotone function $f$, 
there is a 1-1 correspondence between the prime implicants of $f$
and the set $\min_b(f)$.
Namely: \pp
(1) for every term $t$ in the minimal DNF representation for $f$,
the assignment $\min_b(t)$ is in $\min_b(f)$.
\pp
(2) $|\min_b(f)|=|DNF(f)|$.
\end{claim}


We would also use the notion of a least upper bound of a Boolean 
function \cite{SelmanKa91}, which can sometimes be characterized by the
monotone theory.

\begin{definition}[Least Upper-bound]
\label{def:lub}
Let ${\cal F},{\cal G}$ be classes of Boolean functions.
Given $f \in {\cal F}$ 
we say that 
$g \in {\cal G}$ is a 
${\cal G}$-least upper bound of $f$ if and only if $f \subseteq g$ and
there is no $f' \in {\cal G}$ such that 
$f \subseteq f' \subset g$.
\end{definition}

\begin{theorem}{\bf \cite{KhardonRo94a}}
\label{thm:lub}
Let $f$ be any Boolean function and ${\cal G}$ a class of all
Boolean functions with basis $B$. Then, $f^B_{lub}$ defined as
$$ f^B_{lub} = \And_{b \in B} \mon_b(f)$$
is the ${\cal G}$-least upper bound of $f$.
\end{theorem}

For the class of Horn expressions we have two ways to express the least
upper bound. One using the monotone theory, and one using the $closure$
operator:

\begin{theorem}{\bf \cite{DechterPe92,KautzKeSe95,KhardonRo94a}}
\label{thm:Hlub}
Let $f:\cuben\rightarrow\zerone$ be a Boolean function. Then 
$f^{B_H}_{lub}=closure(f)$, and $char(f^{B_H}_{lub})\subseteq f$.
\end{theorem}

For example consider the function
$ f = (bc\ra d)(cd\ra b)(bc\ra a)(a\vee b\vee c \vee \ov{d})$. 
The function $f$ satisfies all the assignments as $W$ above except
for $0001$. However,  \\ $intersect(\{0101,1001\})=0001$, and
therefore $f^{B_H}_{lub}=W$.

\subsection{The Computational Problems}

This section includes definitions for all the
problems discussed in this paper.
Let $H$ be a CNF expression in Horn form, and let $char(H)$ be its set of
characteristic models.
The translation problems considered are:

\vspace{2mm}
\pp
{\bf CCM:} Computing Characteristic Models \\ 
Input: a Horn CNF $H$.  \\
Output: the set $char(H)$.

\vspace{2mm}
\pp
{\bf SID:} Structure Identification (Computing Horn Expressions)\\ 
Input: a set of assignments $\Gamma$.   \\
Output: a Horn CNF $H$, such that $\Gamma = char(H)$.

\vspace{2mm}
\pp
{\bf HTR:} Hypergraph Transversals (Dualization of Monotone Expressions)\\ 
Input: a monotone CNF expression $C$. \\
Output: a monotone DNF expression $D$, such that $C\equiv D$.

\vspace{2mm}
\pp
The decision problems discussed:
%
\vspace{2mm}
\pp
{\bf CMI:} Characteristic Models Identification \\ 
Input: a Horn CNF $H$, and a set $G$ of satisfying assignments of $H$. \\
Output: Yes iff $char(H) \subseteq G$.  \\
Note: The condition is equivalent to $H\models closure(G)$, and essentially
also to $G=char(H)$.

\vspace{2mm}
\pp
{\bf EOC:} Entailment of Closure \\ 
Input: a Horn CNF $H$, a set $G$ of assignments.  \\
Output: Yes if and only if $H\models closure(G)$.

\vspace{2mm}
\pp
We also discuss the following variant of CMI:

\vspace{2mm}
\pp
{\bf CMIC:} Characteristic Models Identification with Counter example \\
Input: a Horn CNF $H$, a set $G$ of satisfying assignments of $H$. \\
Output: If $Char(H)\subseteq G $ then output Yes. 
Otherwise, output No and supply 
a counter example $x\in Char(H)\setminus G$.





\subsection{Polynomial Time Algorithms and Reductions}

As mentioned above we need
to define algorithms that are polynomial with respect to their output.
There is more than one way to give such a definition. (A discussion of
this issue is given by Eiter and Gottlob \citeyear{EiterGo94}.)
We use the weakest\footnote{
Other related notions which we do not use here are ``enumeration with 
polynomial delay" and ``enumeration with incremental polynomial delay"
\cite{EiterGo94}.
These require that the algorithm will compute the elements of its output
one at a time, and restrict the time delay between consecutive outputs.
Incremental polynomial delay allows the delay to depend on the problem
size and on the number of elements computed so far.
Polynomial delay 
is stricter in that it requires dependence only on the problem size.
Both of these notions are stricter than output polynomial algorithms
since the latter may wait a long time before computing its first output.
Unfortunately, most of our reductions yield output polynomial algorithms, and
we cannot guarantee that the stronger notions hold.
}
of those which is called an {\em output polynomial}
algorithm.

When the output of a problem $P$ is uniquely defined,
we say that an algorithm $A$
is an output polynomial algorithm for $P$  if it solves $P$ correctly in
time which is polynomial
in the size of its input and output.
This is the case with HTR, and CCM.

When the output of a problem $P$ is not uniquely defined,
we consider the shortest permissible output $O(I)$ for input $I$.
We say that an algorithm $A$
is an output polynomial algorithm for $P$  if it solves $P$ correctly in
time which is polynomial
in the size of its input $I$ and the size of $O(I)$.
We note that for SID the output is not uniquely defined since there is
no unique minimal representation for Horn functions.

We define polynomial reductions with respect to an oracle
(i.e. we use Turing reducibility \cite{GareyJo79}).
A problem P1 is {\em polynomially reducible} to a problem P2
if there is an output polynomial algorithm that solves P1 when given 
access to (1) an output polynomial subroutine for P2, and (2)
a polynomial bound\footnote{
That is, a polynomial in the dimension of the problem
(the number of variables), the input size, and the output size.}
on the running time of the subroutine.


\section{Translating is Equivalent to Deciding }

In this section we show that the problems CCM, SID, CMI, and CMIC
are equivalent under polynomial reductions. 
Namely, both translation problems are solvable in polynomial time if and
only if the corresponding decision problem CMI is solvable in polynomial
time.


\begin{theorem}
\label{thm:polyequ} 
The problems CCM,SID,CMI, and CMIC are equivalent under polynomial reductions.
\end{theorem}
\begin{proof}
The proof is established in a series of lemmas.
In particular we show that 
$\mbox{CMIC} \leq \mbox{CMI} \leq \mbox{SID} \leq \mbox{CMIC}$, and that
$\mbox{CMI} \leq \mbox{CCM} \leq \mbox{CMIC}$, where $\leq$ 
denotes ``is polynomially reducible to", in
Lemma~\ref{lm:cmiccmi}, Lemma~\ref{lm:cmisid},
Lemma~\ref{lm:sidcmic}, Lemma~\ref{lm:cmicccm},
and Lemma~\ref{lm:ccmcmic} respectively.
\end{proof}

\begin{lemma}
\label{lm:cmiccmi}
The problem CMIC is polynomially reducible to the problem CMI.
\end{lemma}

Before presenting the proof consider how a similar result is
achieved for the satisfiability problem \cite{GareyJo79}.
Namely, 
how a decision procedure for satisfiability  can be used to construct an
algorithm that finds a satisfying assignment if one
exists.
Suppose we have a formula $C$, and that we know that it is satisfiable.
(We used the decision procedure to find that out.)
Our task is to find a satisfying assignment  for it.
What we do is substitute $x_1=0$ into $C$ yielding a formula
$C^0$ with $n-1$ variables. 
The formula $C^0$ is satisfiable if and only if $C$ has a satisfying
assignment in which $x_i=0$.
We run the decision procedure on $C^0$. 
If the answer is Yes then we know
that $C$ has a satisfying assignment in which $x_i=0$.
If the answer is No then since $C$ is satisfiable, it must have
a satisfying assignment in which $x_1=1$.
In either case we found a substitution for $x_1$ which guarantees
the existence of a satisfying assignment. All we have to do is to
recurse with this procedure on $C^0$.

An example can clarify this a bit more. Suppose we have the expression
$C=(a\vee c)(b\vee \ov{c})$ which is satisfiable. To find a satisfying 
assignment we substitute $a=0$ to get $C^0=(c)(b\vee\ov{c})$, and run the 
decision procedure on $C^0$. The answer is Yes, and therefore we continue
with $C^0$. We next substitute $b=0$ to get $C^{00}=c\ov{c}$. We run the 
decision procedure again, and the answer is No. Therefore we conclude
that we must substitute $b=1$ instead of $b=0$. This yields
$C^{01}=c$. We then continue to find that $c$ must be assigned 1
and altogether we find the satisfying assignment $abc=011$.

We would like to use the same trick here.
However, $G$ is given as a set of models and we cannot perform this
substitution procedure as easily\footnote{Furthermore,
the closed form  one can derive using the monotone theory
\cite{KhardonRo94a} does not seem to be useful.}.
Nevertheless, as the proof shows something similar can be done.


\begin{proof}
First observe that we have a solver for CMI. Therefore if the answer is
Yes we have no problem, we can simply answer Yes.
A problem arises in the case where the answer is No. In this case CMI
is happy with saying No, but CMIC must provide a counter example.

Formally, we get $H,G$ as input to CMIC and an algorithm $A$ to solve CMI.
We run $A$ on $H,G$ as an input, and if $A$ replies Yes we reply Yes.
Otherwise we know that there exits an 
$x\in char(H)\setminus G$. We need to find such a model and return it as
the output of CMIC.

Consider first the easier task of finding $x\in H\setminus closure(G)$;
the assignment $x$ is a {\em witness} for the fact $H\not \models closure(G)$.

Recall the substitution trick from above, and
observe that for $x_i=1$ a similar substitution works.
For $H$ we simply perform the substitution to get an expression $\tilde{H}$, 
and for $G$ we remove any $z\in G$ in which $z_i=0$ to get the set
$\tilde{G}$. 
We claim that there is a witness for $H,G$ with $x_i=1$ if and only if
there is a witness for $\tilde{H},\tilde{G}$.
This follows from the fact that $x\in closure(G)$ and $x_i=1$
if and only if $x\in closure(\tilde{G})$.
To see that, let
$x\in closure(G)$, such that  $x_i=1$;
if $x=intersect(S)$, and $y\in S$ then $y_i=1$, and therefore
$x\in closure(\tilde{G})$.
Also if $x\in closure(\tilde{G})$ then $x\in closure(G)$.
Therefore, if there is a witness  $x$ with $x_i=1$
then we can detect this fact by presenting $A$ with $\tilde{H},\tilde{G}$ as
input (on which it will say No).

This however does not work for $x_i=0$. In this case an element
in the closure requires at least one element in $S$ with $y_i=0$, 
but we have no information on the other elements.
Therefore we can not perform the recursion in the case 
where substitution of $x_i=0$ is required.

We circumvent this problem using the following iterative procedure. 
In each stage we try to turn one more variable to $1$. 
For all $i$, we make the experiment described above of substituting $x_i=1$.
If the answer is No, for some $i$, we can proceed to the next stage, just
as before (ignoring tests for other values of $i$).
If the answer is Yes for all $i$, then we know that for each $x_i$ 
that did not receive a value so far, 
there is no witness with $x_i=1$, so the only possible witness
is the one assigning $0$ to all the variables.
We return the witness  $x\in \cuben$ arrived at, by the above
substitutions, as the counter example of CMIC.

>From the construction it is clear that $x\in H\setminus closure(G)$, but 
the requirement of CMIC is that $x\in char(H)\setminus G$. We claim that
this stronger condition holds. Suppose not, and let $S\subseteq char(H)$
be such that $x=intersect(S)$. Then clearly $S$ is not a subset of $G$ or
otherwise $x\in closure(G)$. Let $y\in S\setminus G$, then since
$x=intersect(S)$, we get $x<_{0^n} y$. Namely, if $x_i=1$ then $y_i=1$.
But this is a
contradiction, since in the last run of the algorithm $A$ for CMI, 
it was concluded that no more variables could be set to 1, while still
maintaining a witness.
\end{proof}

We exemplify the proof using the function 
$W = (bc\ra d)(cd\ra b)(bc\ra a)$ presented in the introduction.
Recall that
$char(W)=\{ 0010, 0101, 1001, 1010, 1100, 1101, 1111  \}$, and suppose 
that so far we found 
$G=\{ 0010, 1001, 1010, 1100, 1101, 1111  \}$. That is, all but   
the model $0101$.
We run CMI on $W,G$ and, since $G$ does not include all the characteristic 
models, it answers No. In order to find the counter example we make
4 separate substitutions, one for each variable substituted to 1.

Consider the substitution with $b=1$.
This yields $\tilde{W}=(c\ra d)(c\ra a)$, and 
$\tilde{G}=\{1s00,1s01,1s11\}$, where we use $s$ to mark that the variable 
$b$ was substituted. We run CMI on $\tilde{W},\tilde{G}$ and it finds
out that there is a counter example 
(the assignment $0s01$ is in $\tilde{W}$
but not in $closure(\tilde{G})$), and therefore it answers No.
That means we can continue our algorithm with $b=1$. We forget all
the information from the other substitutions (that were not considered in
detail) and continue to the next step.

In the next step we substitute 1 to each of $a,c,d$. Consider first the
substitution for $a$. 
This yields $\tilde{W}=(c\ra d)$ and 
$\tilde{G}=\{ss00,ss01,ss11\}$. Running CMI on this pair we get
the answer Yes. Namely $\tilde{W}=closure(\tilde{G})$.
Consider now the substitution for  $d$. 
This yields $\tilde{W}=(c\ra a)$ and 
$\tilde{G}=\{1s0s,1s1s\}$. Running CMI on this pair we get
the answer No (since $0s0s$ is a counter example).
We can therefore recurse on this value.

In the next iteration both substitutions for $a$ and for $c$, yield
the answer Yes, and therefore we substitute 0 to both
to get the final counter example $abcd=0101$.

Using this example it is easy to see that one can improve the running time
of the reduction by simply remembering the attributes for which we received
the answer Yes. These attributes will have to get the value 0 in the end.
In this way we can scan the variables one by one, and recurse on the 
first that yields the answer No.  This requires only $n$ calls to CMI. 

\begin{lemma}
\label{lm:cmisid}
The problem CMI is polynomially reducible to the problem SID.
\end{lemma}
\begin{proof}
We are given 
an output polynomial time algorithm $A$ for
SID,  and a polynomial bound on its running time (that is, a polynomial 
in the number of variables $n$, the input size, and the output size).
Given $H,G$ as input to CMI, 
we run $A$ on $G$ until it stops and outputs $H'$ or until it exceeds
its time bound (with respect to the size of $H$). 
In the first case we check whether $H=H'$ (which can be done in polynomial
time \cite{DowlingGa84}) and answer accordingly. 
In the
second case we know that the real Horn expression which corresponds to $G$ 
is larger than $H$ and therefore we answer No.
\end{proof}

The proof of the next lemma
draws on previous results in computational
learning theory. In this framework a function $f:\cuben\rightarrow\zerone$
is hidden from a learner that has to reproduce it by accessing certain
``oracles". A membership query allows the learner to ask for the value of the
function on a certain point.

\begin{definition}
A membership query oracle for a function $f:\cuben\rightarrow\zerone$,
denoted $MQ(f)$, is an oracle that when presented with $x\in \cuben$
returns $f(x)$.
\end{definition}

An equivalence query allows the learner to find out whether a hypothesis
he has is equivalent to $f$ or not. In case it is not equivalent, the
learner is supplied with a counter example.

\begin{definition}
An equivalence query oracle for a function $f:\cuben\rightarrow\zerone$,
denoted $EQ(f)$, is an oracle that when presented with a hypothesis
$h:\cuben\rightarrow\zerone$,
returns Yes if $f\equiv h$. Otherwise it returns No and a counter example
$x$ such that $f(x)\not = h(x)$.
\end{definition}

\pp
We use a result that has been obtained in this framework.

\begin{theorem}{\bf \cite{AngluinFrPi92}}
\label{thm:afp}
There is an algorithm $A$, that when given access to $MQ(f)$ and $EQ(f)$,
where $f$ is a hidden Horn expression, runs in time polynomial 
in the number of variables and in the size of $f$,
and outputs a Horn expression $H$ which is equivalent to $f$.

The hypothesis $h$, in the algorithm's accesses to $EQ(f)$, 
is always a Horn expression.
\end{theorem}

\pp
The following lemma, and the simulation in its proof, are implicit 
in previous works \cite{DechterPe92,KautzKeSe95,KivinenMa94}. 

\begin{lemma}
\label{lm:sidcmic}
The problem SID is polynomially reducible to the problem CMIC.
\end{lemma}
\begin{proof}
We are
given $G$ as input to SID,  and a polynomial time algorithm $C$ for CMIC.
Our algorithm
will run the algorithm $A$ from Theorem~\ref{thm:afp}
and answer the $MQ$ and $EQ$ queries that $A$ presents.

Given $x\in\cuben$ for $MQ$ the algorithm tests whether $x\in closure(G)$.
This can be done by testing whether $x$ is equal to the intersection of
all elements $y$ in $G$ such that $y\geq x$.

Given a Horn expression $h$ for $EQ$ (the theorem guarantees that the
hypothesis is a Horn expression), we have to test whether $h\equiv
closure(G)$. We first test whether $closure(G)\subseteq h$, which is
equivalent to $closure(G)\implies h$.  
Theorem~\ref{thm:Hlub} together with
Theorem~\ref{thm:deduct} imply that if the answer is No, then 
for some $x\in G$, $h(x)=0$. Such an $x$ is a counter example for the
equivalence query, and the test can be performed simply by evaluating $h$ on
all the assignments in $G$.

If $closure(G)\implies h$, namely all the assignments in $G$ satisfy $h$,
we present $h,G$ as input to the algorithm $C$ for the problem CMIC.
The input to CMIC is legal. $C$ may answer Yes, meaning
$char(h)\subseteq G$, which implies $h\subseteq closure(G)$. 
In this case we answer Yes to the equivalence query. 
Otherwise $C$ says No and supplies a counter example 
$x\in char(h)\setminus G$. Since $G\subseteq h$
we get $x\in h\setminus closure(G)$ and therefore we can pass $x$ on as 
a counter example to the equivalence query.
\end{proof}

\pp
We next consider the problem CCM:

\begin{lemma}
\label{lm:cmicccm}
The problem CMI is polynomially reducible to the problem CCM.
\end{lemma}
\begin{proof}
We are given 
an output polynomial  algorithm $C$ for CCM,
and a polynomial bound on its running time (that is, a polynomial 
in the number of variables $n$, the input size, and the output size).
Given $H,G$ as input to CMI,  
we run $C$ on $H$ until it stops and outputs $G'$
or until it exceeds its time bound (with respect to
the size of $G$). 
In the first case we compare $G$ and $G'$ and answer accordingly.
In the
second case we know that the set of characteristic models of $H$ 
is larger than $G$ and therefore we answer No.
\end{proof}

\begin{lemma}
\label{lm:ccmcmic}
The problem CCM is polynomially reducible to the problem CMIC.
\end{lemma}
\begin{proof}
Given $H$ as input for CCM,
an algorithm for CMIC can be used repeatedly to
produce the elements of $char(H)$.

We start with $G=\emptyset$.
In each iteration we run CMIC on $H,G$ to get a new characteristic model
which we add to $G$. Once we find all the characteristic models 
CMIC will answer Yes.
(In fact, if CMIC is polynomial in its input size then 
we get an ``incremental polynomial algorithm" \cite{EiterGo94}
which is even stronger than ``output polynomial" as required here.)
\end{proof}

\section{The Relation to Hypergraph Transversals}

In this section we establish the relation to the hypergraph transversal
problem. We first show that our problems are at least as hard as HTR.
We then consider two relaxations of SID and CCM. The first relaxation
considers redundant representation for Horn expressions, which includes
all the prime implicates. The second relaxation considers computing prime
implicants instead of characteristic models. Both of these relaxations
enjoy sub-exponential algorithms. It is shown, however, that the relaxations
do not help
in the general case, as a result of exponential gap in the size
of the corresponding representations.

\subsection{The Reduction to HTR}
\label{sec:dual}

The problem HTR is defined as computing a DNF representation
for a monotone function given in its CNF form.
It is easy to observe that this is equivalent to computing a CNF
representation for a monotone function given in its DNF form.
(We can simply exchange the $\vee$ and $\wedge$ operations to get one
problem from the other). We can therefore assume that the input for HTR
is given as either a DNF or a CNF.
Another useful observation is that renaming the variables does not change
the problem. Therefore if we rename every variable as its negation
(namely, replace every $x_i$ with $\ov{x_i}$), we get the equivalent
problem of translating between functions which are monotone with respect to
the order relation $\leq_{1^n}$. We call such functions {\em anti-monotone}.
This is useful since anti-monotone functions have CNF representations in
which all variables are negated, which is a special case of Horn
expressions. 
Having these observations, the next two theorems follow almost immediately
>from the definitions, given the correspondence between minimal elements
and prime implicants described in Claim~\ref{cl:size}.
The following result has been stated as an open problem 
by Kavvadias et. al. \citeyear{KavvadiasPaSi93}.

\begin{theorem}
\label{thm:hardp1}
The problem HTR is polynomially reducible to the problem CCM.
\end{theorem}
\begin{proof}
Let $A$ be  an algorithm for the problem
CCM. We construct  an algorithm $B$ for the problem HTR.
%
We may assume that the input is an anti-monotone CNF, $C$,  and we 
want to compute its anti-monotone DNF representation. 

The basic idea is that using Claim~\ref{cl:size} we know how to compute 
the DNF from $\min_{1^n}(C)$, and that the latter is a subset of the 
characteristic models. So all we need to do is let $A$ compute
the characteristic models, identify the set $\min_{1^n}(C)$, 
and compute the DNF.

More formally, the algorithm $B$ 
runs $A$ to compute $\Gamma=char(C)=\min_{B_H}(C)$, 
and computes the set
$\Gamma_{1^n}=\{z\in \Gamma\ |\ \forall y\in \Gamma, z\not<_{1^n} y\}$. 
Namely the
elements of $\Gamma$ which are minimal with respect to the order relation
$b=1^n$. It then computes the anti-monotone DNF expression
$D=\vee_{z\in \Gamma_{1^n}}\wedge_{z_i=0} \ov{x_i}$, 
which it outputs.

The correctness of the algorithm follows from
Claim~\ref{cl:size} which guarantees that the computation of the DNF 
>from the set of characteristic models is correct.

As for the time complexity we observe,
using Claim~\ref{cl:size},
that $\Gamma$ is not
considerably larger than the size of the DNF. This is true since 
for all $b$,
$|DNF(f)|=|\min_{1^n}(f)|\geq |\min_{b}(f)|$, and $|B_H|=n+1$.
\end{proof}

To exemplify the above reduction, suppose 
that we have only three variables $a,b,c$, and that
the input is $C=(\ov{a} \vee \ov{b})(\ov{b}\vee\ov{c})$. 
(The satisfying assignments are $000, 001, 010, 100, 101$, and
the required DNF expression is $\ov{a}\ \ov{c}\vee\ov{b}$.)
The algorithm $A$ will compute the set of characteristic models
$char(C)=\{101,010,100,001\}$, from that we find that 
$min_{1^n}(C)=\{101,010\}$. The term which corresponds to 101
is $\ov{b}$, and the term which corresponds to 010 is $\ov{a}\ \ov{c}$
and indeed we get the right DNF expression.


Using the monotone theory one can give a simple proof for the
following theorem, which has already been proved by Kavvadias et. al. 
\citeyear{KavvadiasPaSi93}. 

\begin{theorem}{\bf \cite{KavvadiasPaSi93}}
\label{thm:hardp2}
The problem HTR is polynomially reducible to the problem SID.
\end{theorem}


We note that 
both theorems can be deduced by combining results in database theory
\cite{EiterGo94,EiterGo91,BiochIb93} and using the above mentioned 
equivalence with problems in database theory \cite{KhardonMaRo95}.



\subsection{Enumerating Prime Implicates}

Having obtained the hardness results in the previous sub-section,
a natural question is whether CCM, and SID are as easy as HTR.
This would help
settle the exact complexity of the problems discussed, and 
more importantly
would imply a sub-exponential algorithm for the problem.
While no such reduction has been found,
we show here that it holds in a special case.
We show, however, that the solution obtained in this way may need
exponential time in the general case. 

This result has already been obtained in the database domain
\cite{EiterGo91}, where restrictions of functional dependencies to be in
MAK form is discussed.
Our argument, however, can be generalized to richer languages, and in
particular holds for the family of $k$-quasi Horn expressions
defined below.

In particular we relax the problems so as to use 
the largest Horn expression  for a function 
instead of using a small Horn expression.
In this case the problem SID amounts to computing
all the (Horn) prime implicates
of the function identified by $\Gamma$.
For CCM we have to compute the set of characteristic models given the set of
all prime implicates rather than a small expression.

We would use the following example to illustrate the notions in this 
sub-section.
Consider the function $W=(a\ra b)(c\ra b)(\ov{b}\vee\ov{d})$.
The satisfying assignments of $W$ are $W=\{0000,0001,0100,0110,1100,1110\}$,
and the characteristic models are $char(W)=\{0001,0110,1100,1110\}$.
One can verify that $W\models(\ov{c} \vee \ov{d})(\ov{a}\vee\ov{d})$,
and that these are the only additional Horn prime implicates of $W$.

For CCM,
this section asks whether it is easier to compute the characteristic models
starting with the equivalent expression 
$W=(a\ra b)(c\ra b)(\ov{b}\vee\ov{d})(\ov{c} \vee \ov{d})(\ov{a}\vee\ov{d})$.
For SID the question is whether it is easier to output the whole set
rather than just a minimal subset.
These are relaxations of the problems since, an algorithm for SID is
allowed more time to compute its output, and CCM is given more information
and more time for its computation.

Let $f$ be a Horn expression, then using 
the monotone theory representation (Equation~(\ref{eq:monotone}))
we know that 
\begin{equation}
\label{eq:decomp2}
f=\wedge_{b\in B_H} \mon_b(f).
\end{equation}
Recall that 
$B_H=\{u\in\cuben\ |\ \mbox{ weight}(u) \geq n-1\}$,
and denote by $b^{(i)}$, $1\leq i\leq n$, the assignment with $x_i$ 
set to zero and all
other bits set to 1, and by $b^{(0)}$ the assignment $1^n$.
In our example $b^{(0)}=1111$, and $b^{(1)}=0111$.


Let $D_i$ be the set of 
clauses that are falsified by $b^{(i)}$,
and let ${\cal G}_i$ denote the language of all CNF expressions 
with clauses from $D_i$.
In our example, with four variables $a,b,c,d$, 
clauses in $D_1$ may have $b,c,d$ as negative literals 
and $a$ as a positive literal. That is, $(\ov{a}\vee \ov{b})\not\in D_1$,
but $(a \vee \ov{b})\in D_1$ and $(\ov{b}\vee\ov{c})\in D_1$.

Theorem~\ref{thm:lub} implies that $\mon_{b^{(i)}}(f)$
is equal to the least upper bound of $f$ in ${\cal G}_i$. Namely,
the intersection of all clauses in $D_i$ which are implied by
$f$. 
Define $PI(f,i)$ to be the set of prime implicates of $f$ with respect
to $b^{(i)}$. Formally:
\[PI(f,i) = \{ d\in D_i | f\models d \mbox{ and } 
	   \forall d'\subseteq d, f\not\models d' \}.  \]

Using this notation we get:
\begin{equation}
\label{eq:decompose}
 \mon_{b^{(i)}}(f) = \bigwedge_{ d\in PI(f,i) } d. 
\end{equation}

Going back to the example $W$, we have:
\begin{eqnarray*}
PI(W,0) & = & 
	(\ov{b}\vee\ov{d})(\ov{c} \vee \ov{d})(\ov{a}\vee\ov{d}) \\
PI(W,1) & = & 
(\ov{b}\vee\ov{d})(\ov{c} \vee \ov{d})   \\
PI(W,2) & = & 
(a\ra b)(c\ra b)(\ov{c} \vee \ov{d})(\ov{a}\vee\ov{d})  \\
PI(W,3) & = & 
(\ov{b}\vee\ov{d})(\ov{a}\vee\ov{d})  \\
PI(W,4) & = & \mbox{\rm true.}
\end{eqnarray*}


Note that  the partition of the prime implicates of $f$ is not
disjoint. In particular, the anti-monotone prime implicates
(except for $\nxa\vee\nxb\vee\ldots\vee \ov{x_n}$ if it is a prime
implicate) appear in several $PI(f,i)$ sets.
Equation~(\ref{eq:decomp2}) tells us that we can decompose
the function into $n+1$,  $b^{(i)}$-monotone functions. 
Equation~(\ref{eq:decompose}) tells us how to decompose the clauses of
the function, and the monotone theory tells us how to decompose the 
characteristic models. These observations lead to the following theorem:


\begin{theorem}
The problem CCM, when the input is given as the set of {\em all} Horn
prime implicates, is polynomially equivalent to HTR.
\end{theorem}
\begin{proof}
First observe that the reduction in Theorem~\ref{thm:hardp1}
uses an anti-monotone function, which has a
unique Horn representation. Namely the smallest and the largest
representations are the same in this case. This implies that the problem
remains as hard as HTR in this special case.

For the other direction, we first partition the input into the sets
$PI(f,i)$, and then use a procedure for HTR in order to translate each
set to a DNF representation. Then using Claim~\ref{cl:size} we translate
the DNF expression to the set of minimal assignments.
The crucial point is that we have DNF representations for the functions
$\mon_{b^{(i)}}(f)$ rather than for $f$. This implies that each term in
these DNF representations is represented as an element in $char(f)$
and therefore the reduction is polynomial. (We may get some of
the elements in $char(f)$ more than once, but at most $n$ times,
which is still polynomial.)
\end{proof}
In our example, we get the following DNF expressions and their translation
into assignments:
\begin{eqnarray*}
PI(W,0) & = &   
		\ov{a}\ \ov{b}\ \ov{c} \vee \ov{d} 
		\Rightarrow \ \ \ \Gamma_0= 0001,1110 \\
PI(W,1) & = & 
		\ov{b}\ \ov{c} \vee \ov{d}  \ \  \,
		\Rightarrow \ \ \ \Gamma_1= 0001,0110 \\
PI(W,2) & = & 
		b \ov{d} \vee \ov{a}\ov{c}  \   \  
		\Rightarrow \ \ \ \Gamma_2= 1110,0001 \\
PI(W,3) & = & 
		\ov{a}\ \ov{b} \vee \ov{d}  \  \  \,
		\Rightarrow \ \ \ \Gamma_3= 0001,1100 \\
PI(W,4) & = & \mbox{\rm true}               \ \ \ \  \ \  
		\Rightarrow \ \ \ \Gamma_4= 1110 
\end{eqnarray*}


Similarly we get for SID:
\begin{theorem}
The problem SID, when the output required is {\em all} Horn
prime implicates, is polynomially equivalent to HTR.
\end{theorem}
\begin{proof}
The proof is similar to the proof of the previous theorem.
The hardness follows from Theorem~\ref{thm:hardp2}.

For the other direction, assume we get as input a set $\Gamma$,
and  an algorithm $A$ for HTR.
We first partition $\Gamma$ into sets
$\Gamma_i$ according to minimality with respect to $b^{(i)}$.
(Note that the sets are not disjoint.) 
Then we use Claim~\ref{cl:size} to transform each $\Gamma_i$ into a DNF
expression for the function $\mon_{b^{(i)}}(f)$.
For each such DNF expression we run the procedure $A$ 
to compute its CNF representation. By Equation~(\ref{eq:decomp2}),
the intersection, with respect to $i$,
of these CNF expressions is the Horn expression we need.
\end{proof}

In the example, we simply start with the sets $\Gamma_i$
and use the same equations as above going in the other direction.
>From the above two theorems we get the following corollary.

\begin{corollary}
The problems CCM and SID, when the Horn expression is represented 
as the set of {\em all} Horn prime implicates, are polynomially 
equivalent, and are polynomially equivalent to HTR.
\end{corollary}

The equivalence of CCM and SID, in this special case, 
has been observed before in the database domain 
(Heikki Mannila, private communication). In fact this led us to the
results of this section.
As mentioned above a similar result 
for relational databases is reported by Eiter and Gottlob 
\citeyear{EiterGo91} where the restriction is called the MAK form 
for functional dependencies.

\vspace{2mm}
\pp
{\bf Lifting the Restriction:}
The polynomial equivalence to the problem HTR, implies the existence of
sub-exponential
$n^{O(\log n)}$ algorithm for these problems which may have some practical
implications.
However, as the following example shows one cannot apply it to solve the
general case of the problem SID.
Aizenstein and Pitt \citeyear{AizensteinPi95} 
present some functions with
interesting properties.
These functions can be manipulated
to create examples with the following properties:
(1) $f$ has a short Horn expression,
(2) $|char(f)|$ is small, (3) the number of Horn ``prime implicates"
is exponential.
In particular
$$f=(\ov{x_1}\vee \ov{x_2}\vee \ldots \vee \ov{x_m})
     \wedge (x1 \vee \ov{y_1}) 
     \wedge (x2 \vee \ov{y_2})
     \wedge \ldots 
     \wedge (x_m \vee \ov{y_m})      $$
has these properties.
The set of prime implicates include all the disjunctions $(b_1\vee
b_2\vee\ldots\vee b_m)$ where $b_i\in\{\ov{x_i},\ov{y_i}\}$.

We show by case analysis that the set
of characteristic models is small. Observe 
that in order to satisfy $f$,
at least one of the $x_i$ variables must be assigned 0, and that if
$x_i=0$ then $y_i$ must also be assigned 0.

Consider first the set $\min_{1^{2m}}(f)$. Notice that if, for some $j$,
$x_j=y_j=0$
and all the other variables are set to 1, then $f$ is satisfied.
This contributes exactly $m$ assignments to $\min_{1^{2m}}(f)$.
For $m=3$ and variable ordering $x_1 x_2 x_3 y_1 y_2 y_3$, this yields
the assignments $011011$, $101101$, $110110$.

Consider next $\min_{b^{(x_i)}}(f)$. Namely, the basis element in which
$x_i=0$. 
To satisfy $f$,
if $x_i=0$ then $y_i$ must be 0, and as before we can set all
other variables to 1. If $x_i=1$ then there must be another variable $x_j$
which is set to 0. In this case $y_j$ must also be 0. Therefore
$\min_{b^{(x_i)}}(f) = \min_{1^{2m}}(f)$. 

Lastly, consider $\min_{b^{(y_i)}}(f)$. Namely the basis element in which
$y_i=0$. 
Observe that  $f$ is anti-monotone in $y_i$. Namely, given any satisfying
assignment with $y_i=1$, by flipping $y_i$ to $0$ we get another satisfying
assignment, which  is smaller than the original according to
$\leq_{b^{(y_i)}}$.
Therefore, we may assume that $y_i=0$.
If $x_i=0$ then we can set all other variables to 1.
If $x_i=1$ then there must be another variable $x_j$ which is set to 0, and
therefore also $y_j=0$. This assignment is 2 bits away from $b^{(y_i)}$
and it is minimal. We get $m$ assignments in this case too.
In our example with $m=3$, and say $i=2$, we get 
the assignments $101101$, $011001$, and $110100$.

Altogether we get $m$ assignments from the first two groups and $m(m-1)$
new assignments from the last and therefore $|char(f)|=m^2$.
This means that arbitrary enumeration of the prime implicates, for a given 
set of models $\Gamma$, is not sufficient for solving SID.


\vspace{2mm}
\pp
{\bf A Generalization:}
While we concentrate in this paper on Horn expressions, we note that
the same arguments and proofs hold in the more general case of 
$k$-quasi Horn expressions. 
These are expressions in CNF form where in every clause there are at
most $k$ positive literals (so that Horn expressions are 
$1$-quasi Horn expressions).
The set 
$B_{H_k}= \{u\in\cuben\ |\ \mbox{ weight}(u) \geq n-k\}$ is a basis
for $k$-quasi Horn expressions, and $\Gamma^{B_{H_k}}_f$ can serve as
the set of characteristic models for $f$ \cite{KhardonRo94a}.
The generalized versions of
CCM and SID, when restricted to hold all prime implicates are still
equivalent to HTR.


\subsection{Enumerating Prime Implicants}

As mentioned above, given a DNF representation for $f$ we can easily
compute the set of characteristic models. One might therefore try to solve
CCM by first translating the Horn expression into a DNF expression and then
computing the characteristic models from this set.
Another possible relaxation is to first compute all the prime implicants of
the function and then to extract a DNF representation from it.
We consider this problem here.
Namely, we consider the problem of enumerating {\em all} the prime implicants
of a Horn expression, and its application for the solution of CCM.

While we have not found a general reduction  from this problem to HTR,
a simple adaption of the algorithm for HTR 
\cite{FredmanKh94} yields an incremental $n^{O(\log^2 n)}$  algorithm
for this problem.
However, as we discuss below, enumeration of prime implicants of a Horn
expression is not sufficient for solving CCM. 
The problem in such an application  is an exponential gap in the sizes of
these representations.

For completeness we sketch  the main ideas of the enumeration algorithm here.
Let $H$ be a Horn expression, and let $D$ be the DNF expression composed of
the prime implicants enumerated so far. The algorithm finds an assignment $x$
which satisfies $H$ and does not satisfy $D$. Using $x$ it is easy to find a
new prime implicant of $H$. The algorithm to find $x$ uses the following
combinatorial fact \cite{FredmanKh94}: either there is a variable $x_i$
that appears in $H\wedge \ov{D}$ with high frequency, or the expression 
$H\wedge \ov{D}$ has ``a lot" of satisfying assignments. In the first case, 
one can recursively solve two sub-problems arrived at by substituting $x_i=0$,
and $x_i=1$ in the expressions $H$ and $D$.
In the second case it is easy to find an assignment $x$ (e.g. by sampling).
The solution of the recursion yields the stated time bound.
For complete details we refer the reader to the article by
Fredman and Khachiyan \citeyear{FredmanKh94}. 
While the analysis there is specialized
for monotone functions it is easy to extend (the first part of) it
for Horn expressions\footnote{
One caveat that we have to tackle is enumerating prime implicants after
$D$ is already equivalent to $H$. This can be done using ``consensus"
operations, which can generate all the prime 
implicants \cite{AizensteinPi95} 
}. 



\vspace{2mm}
\pp
{\bf Lifting the Restriction:}
Denote by $\#PIs(f)$ the number of prime implicants of $f$.
While the representations 
(1) Prime Implicants (PIs), (2) DNF representation,
and (3) Characteristic models,  satisfy the inequalities
$\#PIs(f) \geq |DNF(f)| \geq |char(f)|/n$, 
each of the inequalities may allow for an exponential gap. 
The function 
\begin{eqnarray*}
 f_1 & = & (\nxa\vee\ \nxb\ldots\vee\  \ov{x_{\sqrt{n}-1}} \vee\  x_{\sqrt{n}})
		 \wedge 
    \ldots\wedge 
     (\ov{x_{n-\sqrt{n}+1}} \vee\  \ov{x_{n-\sqrt{n}+2}} \vee\ldots
     \vee\  \ov{x_{n-1}} \vee\  x_n)
\end{eqnarray*}
\cite{KhardonRo94a} shows a gap between (2) and (3). 
The function 
$$f_2=x_1 x_2\ldots x_m \vee \nxa\  \ov{y_1} \vee \nxb \ \ov{y_2}\vee\ldots 
     \vee \ov{x_m} \ \ov{y_m}$$
\cite{AizensteinPi95} shows a gap between (1) and (2). 
(To observe that, notice the similarity between $f_2$ and the dual
of the function from the previous sub-section.)
Both functions are Horn (for $f_2$ by multiplying out we see
that every clause for $f$ is Horn, although its Horn expression is large)
and both have a small set of characteristic models.
These examples show
that enumeration of prime implicants may be an inefficient
way for producing the characteristic models for some functions.

\section{A Related Problem}

In this section we show that a related problem, which is a minor variant of
CCM and SID, is co-NP-Complete.
Recall the definition of EOC:

\vspace{2mm}
\pp
{\bf EOC:} Entailment of Closure \\ 
Input: a Horn CNF $H$, a set $G$ of assignments.  \\
Output: Yes if and only if $H\models closure(G)$.

The important difference between CMI and EOC 
is that the set $G$ is not
required to include only satisfying assignments of $H$. This enables
the following reduction for EOC, while the complexity of CMI is still
open. A similar result in the database domain has been obtained by 
Gottlob and Libkin \citeyear{GottlobLi90}.


\begin{theorem}
\label{thm:eoc}
The decision problem EOC is co-NP-Complete.
\end{theorem}
\begin{proof}
The problem is trivially in co-NP (guess an assignment $x$
and say ``No" if $x\in H\setminus closure(G)$). 

To show its hardness
we reduce co-Monotone 3-SAT to EOC. Monotone 3-SAT \cite{GareyJo79}
is the problem of satisfiability of CNF formulas in which 
in every clause (has 3 literals and) either all the literals are positive 
(we call these clauses monotone) or all the literals
are negated (we call such clauses anti-monotone).
Let $f=M\wedge A$ an instance of Monotone 3-SAT where $M$ denotes a
conjunction of monotone clauses and $A$ is a conjunction of anti-monotone
clauses.
We translate it to the instance of EOC: $H=A$ and 
$\Gamma=\cup_{b\in B_H} min_b(\ov{M})$.
First we claim that the reduction is polynomial.
Note that since $M$ is a monotone CNF, $\ov{M}$ is a
DNF formula in which all the variables are negated, 
and can therefore be written as an anti-monotone CNF formula. 
This implies that $\ov{M}$ is Horn, but we have
it in a DNF representation.
Further computing $\Gamma$ is easy given the DNF representation
of $\ov{M}$, and its size is bounded by $(n+1)$ times the number of 
clauses in $M$.

We now claim that $f$ is satisfiable if and only 
if $H\not\models closure(\Gamma)$.
Assume first that $f$ is satisfiable, and let $x\in A\wedge M$. This implies
that $x\in H$ and $x\not\in \ov{M}$. 
Since $\ov{M}$ is Horn, and the models of Horn functions are closed
under intersection (Theorem~\ref{thm:kks}) we get that
$x\not\in closure(\ov{M})$, and since $\Gamma\subseteq \ov{M}$
$x\not\in closure(\Gamma)$.
Therefore, $H\not\models closure(\Gamma)$.

For the other direction assume $H\not\models closure(\Gamma)$, and let
$x$ be an assignment such that $x\in H$ and $x\not\in closure(\Gamma)$.
We get that $x\in A$, and since by 
Theorem~\ref{thm:kks} and Theorem~\ref{thm:same} 
$\ov{M}=closure(\Gamma)$ we have $x\not \in \ov{M}$.
So, $x\in A\wedge M$ and $f$ is satisfiable.
\end{proof}
To exemplify the above reduction consider the function
$$f=(\ov{a}\vee\ov{b}\vee\ov{c})
   (\ov{b}\vee\ov{c}\vee\ov{d})
   (a\vee c\vee d)
   (a\vee b \vee c). $$
This function will be translated into 
$H=(\ov{a}\vee\ov{b}\vee\ov{c}) (\ov{b}\vee\ov{c}\vee\ov{d})$.
The function $\ov{M}=\ov{a}\ \ov{c}\ \ov{d}\vee \ov{a}\ \ov{b}\ \ov{c}$.
The satisfying assignments of $\ov{M}$ are $0000, 0001, 0100$,
and $\Gamma= char(\ov{M})=\{0001, 0100\}$.
Now consider the assignment $x=1000$ which satisfies $f$. Clearly,
$x$ satisfies $H$, and one can check that it is not in the closure of
$\Gamma$.

\section{Conclusions}

Horn expressions and characteristic models are two alternative
representations for the same information and none of the two dominates the
other in the computational services it can support.
The same representations occur in database theory where 
they have a role in the design of relational databases.
%
A natural question is whether we can translate back and forth 
between these representations so as to enjoy the benefits of
both worlds.
In this paper we have studied the computational complexity of these problems.

Our main result is that the two translation problems CCM, and SID, are
equivalent to each other (under polynomial reductions), and that they
are equivalent to the corresponding decision problem CMI.
Namely, translating in either direction is equivalent to deciding
whether a given set of models is the set of 
characteristic models for a given Horn expression.

We have also shown a close relation between our problems and the 
hypergraph transversal problem HTR.
This is a translation problem which is related to many applications
in computer science and in particular to AI.
We have shown that in general CCM, and SID are at least as hard as 
HTR, 
and that in a special case CCM, SID, and HTR are equivalent.

We exhibited examples which show that simple algorithms for enumerating
prime implicants cannot guarantee efficient solution for
CCM, and similarly enumerating prime implicates may not be efficient for SID.
Lastly, we discussed the problem EOC,
a minor modification of CMI, which is co-NP-Complete.
The complexity hierarchy of the problems discussed is depicted in Figure~1.

Some of the results presented in this paper can be obtained from
previous results in database theory, using the
equivalence between
Armstrong relations and characteristic models reported in
a companion paper
\cite{KhardonMaRo95}. 
However, our proofs and exposition
make these results much more accessible.


The exact complexity of CMI, and that of HTR are left as open problems. 
While HTR has a sub-exponential algorithm, the problems CMI might
still be co-NP-Hard.


\acks{
I am grateful to Thomas Eiter, Heikki Mannila, and Dan Roth  for
their comments which lead to some of the results in this paper.
I wish to thank the anonymous referees whose comments helped improve the
presentation, and Dimitris Kehagias for his help in proofreading
the paper.
The research for this paper was supported by Center for Intelligent 
Control Systems under ARO contract DAAL03-92-G-0115.}




\bibliographystyle{theapa}
\bibliography{theory,reason,learn,ai,datab,add}

\end{document}










