COMPUTATIONAL ASPECTS OF MONOTONE DUALIZATION: A BRIEF SURVEY
---
paper_title: An O(nm)-time algorithm for computing the dual of a regular Boolean function

paper_content:

Abstract We consider the problem of dualizing a positive Boolean function ƒ: Bn → B given in irredundant disjunctive normal form (DNF), that is, obtaining the irredundant DNF form of its dual ƒ d (x) = ƒ ( x ) . The function f is said to be regular if there is a linear order ≳ on {1,…,n} such that i≳j, xi = 0, and xj = 1 imply ƒ(x) ⩽ ƒ(x + u i − u j ) , where uk denote unit vectors. A previous algorithm of the authors, the Hop-Skip-and-Jump algorithm, dualizes a regular function in polynomial time. We use this algorithm to give an explicit expression for the irredundant DNF of ƒd in terms of the one for ƒ. We show that if the irredundant DNF for ƒ has m ⩾ 2 terms, then the one for ƒd has at most (n − 2)m + 1, and can be computed in O(nm) time. This can be applied to solve regular set-covering problems in O(nm) time.
---
paper_title: Average Case Self-Duality of Monotone Boolean Functions

paper_content:

The problem of determining whether a monotone boolean function is self-dual has numerous applications in Logic and AI. The applications include theory revision, model-based diagnosis, abductive explanations and learning monotone boolean functions. It is not known whether self-duality of monotone boolean functions can be tested in polynomial time, though a quasi-polynomial time algorithm exists. We describe another quasi-polynomial time algorithm for solving the self-duality problem of monotone boolean functions and analyze its average-case behaviour on a set of randomly generated instances.
---
paper_title: Abduction and the Dualization Problem

paper_content:

Computing abductive explanations is an important problem, which has been studied extensively in Artificial Intelligence (AI) and related disciplines. While computing some abductive explanation for a literal χ with respect to a set of abducibles A from a Horn propositional theory Σ is intractable under the traditional representation of Σ by a set of Horn clauses, the problem is polynomial under model-based theory representation, where Σ is represented by its characteristic models. Furthermore, computing all the (possibly exponentially) many explanations is polynomial-time equivalent to the problem of dualizing a positive CNF, which is a well-known problem whose precise complexity in terms of the theory of NP-completeness is not known yet. In this paper, we first review the monotone dualization problem and its connection to computing all abductive explanations for a query literal and some related problems in knowledge discovery. We then investigate possible generalizations of this connection to abductive queries beyond literals. Among other results, we find that the equivalence for generating all explanations for a clause query (resp., term query) χ to the monotone dualization problem holds if χ contains at most k positive (resp., negative) literals for constant k, while the problem is not solvable in polynomial total-time, i.e., in time polynomial in the combined size of the input and the output, unless P=NP for general clause resp. term queries. Our results shed new light on the computational nature of abduction and Horn theories in particular, and might be interesting also for related problems, which remains to be explored.
---
paper_title: Generating all maximal independent sets of bounded-degree hypergraphs

paper_content:

We show that any monotone function with a read-k CNF representation can be learned in terms of its DNF representation with membership queries alone in time polynomial in the DNF size and n (the number of variables) assuming k is some fixed constant. The problem is motivated by the well-studied open problem of enumerating all maximal independent sets of a given hypergraph. Our algorithm gives a solution for the bounded degree case and works even if the hypergraph is not input, but rather only queries are available as to which sets are independent.
---
paper_title: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms

paper_content:

Suppose that an independence system $(E,\mathcal {I})$ is characterized by a subroutine which indicates in unit time whether or not a given subset of E is independent. It is shown that there is no algorithm for generating all the K maximal independent sets of such an independence system in time polynomial in $|E|$ and K, unless $\mathcal {P} = \mathcal {NP}$. However, it is possible to apply ideas of Paull and Unger and of Tsukiyama et al. to obtain polynomial-time algorithms for a number of special cases, e.g. the efficient generation of all maximal feasible solutions to a knapsack problem. The algorithmic techniques bear an interesting relationship with those of Read for the enumeration of graphs and other combinatorial configurations.
---
paper_title: Polynomial-time algorithms for regular set-covering and threshold synthesis

paper_content:

Abstract A set-covering problem is called regular if a cover always remains a cover when any column in it is replaced by an earlier column. From the input of the problem - the coefficient matrix of the set-covering inequalities - it is possible to check in polynomial time whether the problem is regular or can be made regular by permuting the columns. If it is, then all the minimal covers are generated in polynomial time, and one of them is an optimal solution. The algorithm also yields an explicit bound for the number of minimal covers. These results can be used to check in polynomial time whether a given set-covering problem is equivalent to some knapsack problem without additional variables, or equivalently to recognize positive threshold functions in polynomial time. However, the problem of recognizing when an arbitrary Boolean function is threshold is NP-complete. It is also shown that the list of maximal non-covers is essentially the most compact input possible, even if it is known in advance that the problem is regular.
---
paper_title: Dualization of regular Boolean functions

paper_content:

Abstract A monotonic Boolean function is regular if its variables are naturally ordered by decreasing ‘strength’, so that shifting to the right the non-zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: A New Algorithm for Generating Prime Implicants

paper_content:

This paper describes an algorithm which will generate all the prime implicants of a Boolean function. The algorithm is different from those previously given in the literature, and in many cases it is more efficient. It is proved that the algorithm will find all the prime implicants. The algorithm may possibly generate some nonprime implicants. However, using frequency orderings on literals, the experiments with the algorithm show that it usually generates very few ( possibly none) nonprime implicants. Furthermore, the algorithm may be used to find the minimal sums of a Boolean function. The algorithm is implemented by a computer program in the LISP language.
---
paper_title: An incremental method for generating prime implicants/implicates

paper_content:

Given the recent investigation of Clause Management Systems (CMSs) for ArtificialIntelligence applications, there is an urgent need for an efficient incremental method for generating prime implicants. Given a set of clauses F, a set of prime implicants II of F and a clause C"1 the problem can be formulated as finding the set of prime implicants for II U {C}. Intuitively, the property of implicants, being prime implies that any effort to generate prime implicants from a set of prime implicants will not yield any new prime implicants but themselves. In this paper, we exploit the properties of prime implicants and propose an incremental method for generating prime implicants from a set of existing prime implicants plus a new clause. The correctness proof and complexity analysis of the incremental method are presented, and the intricacy of subsumptions in the incremental method is also examined. Additionally, the role of prime implicants in the CMS is also mentioned.
---
paper_title: Learning conjunctions of Horn clauses

paper_content:

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable). The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula. >
---
paper_title: Hypergraph Transversal Computation and Related Problems in Logic and AI

paper_content:

Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional variant, i.e., the recognition of the transversal hypergraph for another hypergraph. We survey some results on problems which are known to be related to computing the transversal hypergraph, where we focus on problems in propositional Logic and AI. Some of the results have been established already some time ago, and were announced but their derivation was not widely disseminated. We then address recent developments on the computational complexity of computing resp. recognizing the transversal hypergraph. The precise complexity of these problems is not known to date, and is in fact open for more than 20 years now.
---
paper_title: Queries and Concept Learning

paper_content:

We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.
---
paper_title: An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension

paper_content:

We show that for hypergraphs of bounded edge size, the problem of extending a given list of maximal independent sets is NC-reducible to the computation of an arbitrary maximal independent set for an induced sub-hypergraph. The latter problem is known to be in RNC. In particular, our reduction yields an incremental RNC dualization algorithm for hypergraphs of bounded edge size, a problem previously known to be solvable in polynomial incremental time. We also give a similar parallel algorithm for the dualization problem on the product of arbitrary lattices which have a bounded number of immediate predecessors for each element.
---
paper_title: Almost all monotone Boolean functions are polynomially learnable using membership queries

paper_content:

We consider exact learning or identification of monotone Boolean functions by only using membership queries. It is shown that almost all monotone Boolean functions are polynomially identifiable in the input number of variables as well as the output being the sum of the sizes of the CNF and DNF representations.
---
paper_title: Exact Transversal Hypergraphs and Application to Boolean µ-Functions

paper_content:

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. The results obtained are applied to monotone Boolean ?-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with ?, ? only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.
---
paper_title: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

paper_content:

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
---
paper_title: An O(mn) algorithm for regular set-covering problems

paper_content:

A clutter L is a collection of m subsets of a ground set E(L) = {x1,…, xn} with the property that, for every pair Ai, Aj ϵ L, Ai is neither contained nor contains Aj, A transversal of L is a subset of E(L) intersecting every member of L. ::: ::: If we associate with each element xj ϵ E(L) a weight cj, the problem of finding a transversal having minimum weight is equivalent to the following set-covering problem ::: min{cTx|MLx ⩾ 1m, xj ϵ {0, 1}, j = 1,…, n} ::: where ML is the matrix whose rows are the incidence vectors of the subsets Ai ϵ L and 1m denotes the vector with m ones. ::: ::: A set-covering problem is regular if there exists an ordering of the variables σ = (x1,…, xn) such that, for every feasible solution x with xi = 1, xj = 0, j < i, the vector x + ej − ei is also a feasible solution, where ei is the ith unit vector. The matrix M of a regular set-covering problem is said to be regular. ::: ::: A regular clutter is any clutter whose incidence matrix is regular. In this paper we describe some properties of regular clutters and propose an algorithm which, in O(mn) steps, generates all the minimal transversals of a regular clutter L and produces the transversal having minimum weight.
---
paper_title: Efficient dualization of O(log n)-term monotone disjunctive normal forms

paper_content:

This paper shows that O(logn)-term monotone disjunctive normal forms (DNFs) φ can be dualized in incremental polynomial time, where n is the number of variables in φ. This improves upon the trivial result that k-term monotone DNFs can be dualized in polynomial time, where k is bounded by some constant.
---
paper_title: Generating Dual-Bounded Hypergraphs

paper_content:

This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and max...
---
paper_title: Polynomial Time Recognition Of 2-Monotonic Positive Boolean Functions Given By An Oracle

paper_content:

We consider the problem of identifying an unknown Boolean function $f$ by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that $f$ is a positive (or monotone) function of $n$ variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in $n$ and $m$, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of $f$. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function $f$ of $n$ variables, decide whether or not $f$ is 2-monotonic and, if $f$ is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.
---
paper_title: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

paper_content:

Consider the problem of identifying minT(f) and maxF(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where minT(f) (maxF(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both minT(f) and maxF(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n2m) time andO(n2m) queries, wherem=|minT(f)|+|maxF(f)|. This answers affirmatively the conjecture raised in Boroset al.Lecture Notes in Comput. Sci.557(1991), 104?115, Boroset al.SIAM J. Comput.26(1997), 93?109, and is an improvement over the two algorithms discussed therein: one usesO(n3m) time andO(n3m) queries, and the other usesO(nm2+n2m) time andO(nm) queries.
---
paper_title: New results on monotone dualization and generating hypergraph transversals

paper_content:

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by \chi(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.
---
paper_title: The Maximum Latency and Identification of Positive Boolean Functions

paper_content:

Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean function f, by using membership queries only, where min T(f) (maxF(f)) denotes the set of minimal true vectors (maximal false vectors) of f. It is known that an incrementally polynomial algorithm exists if and only if there is a polynomial time algorithm to check the existence of an unknown vector for given sets MT\(\subseteq \) min T(f) and MF\(\subseteq \) max F(f). Unfortunately, however, the complexity of this problem is still unknown. To answer this question partially, we introduce in this paper a measure for the difficulty of finding an unknown vector, which is called the maximum latency. If the maximum latency is constant, then an unknown vector can be found in polynomial time and there is an incrementally polynomial algorithm for identification. Several subclasses of positive functions are shown to have constant maximum latency, e.g., 2-monotonic positive functions, Δ-partial positive threshold functions and matroid functions, while the class of general positive functions has maximum latency not smaller than [n/4]+1 and the class of positive k-DNF functions has Ω(√n) maximum latency.
---
paper_title: Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

paper_content:

Given a finite set V, and integers k > 1 and r > 0, denote by A(k, r) the class of hypergraphs A ⊆ 2 V with (k, r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS(A,I): given a hypergraph A and a subfamily I C I(A), of its maximal independent sets (MIS) I(A), either extend this subfamily by constructing a new MIS I ∈ I(A) \ I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A E A(k,r) with k + r ≤ const, problem MIS(A,I) is NC-reducible to problem MIS(A',O) of generating a single MIS for a partial subhypergraph A' of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A(1, c), A(c, 0), and A(2,1), where c is a constant. We also show that, for A ∈ A(k,r), where k + r < const, the problem of generating all MIS of A can be solved in incremental polynomial-time with space polynomial only in the size of A.
---
paper_title: NP-Completeness: A Retrospective

paper_content:

For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary commentary on its origins, its nature, its impact, and on the attributes that have made it so pervasive and contagious.
---
paper_title: An SE-tree-based prime implicant generation algorithm

paper_content:

Prime implicants/implicates (PIs) have been shown to be a useful tool in several problem domains. In model-based diagnosis (MBD), de Kleer et al. (Proc. AAAI-90) have used PIs to characterize diagnoses. We present a PI generation algorithm which, although based on thegeneral SE-tree-based search framework, is effectively an improvement of aparticular PI generation algorithm proposed by Slagle et al. (IEEE Trans. Comput. 19(4) (1970)). The improvement is achieved via adecomposition tactic which is boosted by the SE-tree-based framework. The new algorithm is also more flexible in a number of ways. We present empirical results comparing the new algorithm to the old one, as well as to current PI generation algorithms.
---
paper_title: On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions

paper_content:

Let f : {0,1} n → {0,1} be a monotone Boolean function whose value at any point x ∈ {0,1} n can be determined in time t. Denote by c=Λ I ∈ C ∨ i ∈ I x i the irredundant CNF off, where C is the set of the prime implicates of f. Similarly, let d=∨ J ∈ D Λ j ∈ J x j be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C' ⊆ C and D' ⊆ D such that (C',D') ¬= (C,D), a new term in (C\C')∪(D\D') can be found in time O(n(t+n))+m o(log m) , where m=|C'|+|D'|. In particular, if f(x) can be evaluated for every x ∈ {0,1} n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of Λ, ∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2 polylog(.) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D' =D or C' =C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of Λ, ∨-formulae of depth 3.
---
paper_title: Self-Duality of Bounded Monotone Boolean Functions and Related Problems

paper_content:

In this paper we show the equivalence between the problem of determining self-duality of a boolean function in DNF and a special type of satisfiability problem called NAESPI. Eiter and Gottlob [8] use a result from [2] to show that self-duality of monotone boolean functions which have bounded clause sizes (by some constant) can be determined in polynomial time. We show that the self-duality of instances in the class studied by Eiter and Gottlob can be determined in time linear in the number of clauses in the input, thereby strengthening their result. Domingo [7] recently showed that self-duality of boolean functions where each clause is bounded by (√log n) can be solved in polynomial time. Our linear time algorithm for solving the clauses with bounded size infact solves the (√log n) bounded self-duality problem in O(n2 √log n) time, which is better bound then the algorithm of Domingo [7], O(n3). ::: ::: Another class of self-dual functions arising naturally in application domain has the property that every pair of terms in f intersect in at most constant number of variables. The equivalent subclass of NAESPI is the c-bounded NAESPI. We also show that c-bounded NAESPI can be solved in polynomial time when c is some constant. We also give an alternative characterization of almost self-dual functions proposed by Bioch and Ibaraki [5] in terms of NAESPI instances which admit solutions of a 'particular' type.
---
paper_title: Complexity of Identification and Dualization of Positive Boolean Functions

paper_content:

Abstract We consider in this paper the problem of identifying min T(ƒ) and max F(ƒ) of a positive (i.e., monotone) Boolean function ƒ, by using membership queries only, where min T(ƒ) (max F(ƒ)) denotes the set of minimal true vectors (maximal false vectors) of ƒ. It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the existence of the following algorithms, where ƒ and g are positive Boolean functions: • An incrementally polynomial algorithm to dualize ƒ; • An incrementally polynomial algorithm to self-dualize ƒ; • A polynomial algorithm to decide if ƒ and are mutually dual; • A polynomial algorithm to decide if ƒ is self-dual; • A polynomial algorithm to decide if ƒ is saturated; • A polynomial algorithm in |min (ƒ)| + |max (ƒ)| to identify min (ƒ) only. Some of these are already well known open problems in the respective fields. Other related topics, including various equivalent problems encountered in hypergraph theory and theory of coteries (used in distributed systems), are also discussed.
---
paper_title: Identifying the Minimal Transversals of a Hypergraph and Related Problems

paper_content:

The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $\cal H$, decide if every subset of vertices is contained in or contains some edge of $\cal H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs ${\cal H}_{1}, {\cal H}_{2}$, decide if the sets in ${\cal H}_{2}$ are all the minimal transversals of ${\cal H}_{1}$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.
---
paper_title: Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries

paper_content:

We consider exact learning monotone CNF formulas in which each variable appears at most some constant k times (“read-k” monotone CNF). Let f : l0,1r^n → l0,1r be expressible as a read-k monotone CNF formula for some natural number k. We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f. The algorithm‘s only method of obtaining information about f is through membership queries, i.e., by inquiring about the value f(x) for points x ∈ l0,1r^n. The algorithm yields an incremental polynomial output time solution to the (read-k) monotone CNF/DNF dualization problem. The unrestricted versions remain open problems of importance.
---
paper_title: A New Algorithm for Generating Prime Implicants

paper_content:

This paper describes an algorithm which will generate all the prime implicants of a Boolean function. The algorithm is different from those previously given in the literature, and in many cases it is more efficient. It is proved that the algorithm will find all the prime implicants. The algorithm may possibly generate some nonprime implicants. However, using frequency orderings on literals, the experiments with the algorithm show that it usually generates very few ( possibly none) nonprime implicants. Furthermore, the algorithm may be used to find the minimal sums of a Boolean function. The algorithm is implemented by a computer program in the LISP language.
---
paper_title: Evaluation of an Algorithm for the Transversal Hypergraph Problem

paper_content:

The Transversal Hypergraph Problem is the problem of computing, given a hypergraph, the set of its minimal transversals, i.e. the hypergraph whose hyperedges are all minimal hitting sets of the given one. This problem turns out to be central in various fields of Computer Science. We present and experimentally evaluate a heuristic algorithm for the problem, which seems able to handle large instances and also possesses some nice features especially desirable in problems with large output such as the Transversal Hypergraph Problem.
---
paper_title: Algorithms for inferring functional dependencies from relations

paper_content:

Abstract The dependency inference problem is to find a cover of the set of functional dependencies that hold in a given relation. The problem has applications in relational database design, in query optimization, and in artificial intelligence. The problem is exponential in the number of attributes. We develop two algorithms with better best case behavior than the simple one. One algorithm reduces the problem to computing the transversal of a hypergraph. The other is based on repeatedly sorting the relation with respect to a set of attributes.
---
paper_title: New results on monotone dualization and generating hypergraph transversals

paper_content:

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by \chi(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.
---
paper_title: An SE-tree-based prime implicant generation algorithm

paper_content:

Prime implicants/implicates (PIs) have been shown to be a useful tool in several problem domains. In model-based diagnosis (MBD), de Kleer et al. (Proc. AAAI-90) have used PIs to characterize diagnoses. We present a PI generation algorithm which, although based on thegeneral SE-tree-based search framework, is effectively an improvement of aparticular PI generation algorithm proposed by Slagle et al. (IEEE Trans. Comput. 19(4) (1970)). The improvement is achieved via adecomposition tactic which is boosted by the SE-tree-based framework. The new algorithm is also more flexible in a number of ways. We present empirical results comparing the new algorithm to the old one, as well as to current PI generation algorithms.
---
paper_title: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns

paper_content:

Computing the minimal transversals of a hypergraph is an important problem in computer science that has significant applications in data mining. We present a new algorithm for computing hypergraph transversals and highlight their close connection to an important class of patterns known as emerging patterns. We evaluate our technique on a number of large datasets and show that it outperforms previous approaches by a factor of 9-29 times.
---
paper_title: A Practical Fast Algorithm for Enumerating Minimal SetCoverings

paper_content:

For a set family F defined on a grand set E, a subset of F covering all the elements of E is called a set covering. The enumeration problem of minimal set covering is equal to the enumeration problem of hypergraph dualization, minimal hitting sets, and other other many problems, and have been studied intensively. However, the existence of an output polynomial algorithm for this problem is still open. However, there proposed an algorithm whose average computation time on computational experiments for random generated instances is output polynomial. In this paper, we propose a practical fast algorithm obtained by improving this algorithm, and by computational experiments, show that the average computation time for randomly generated instances is O(|E|) per output, by computational experiments.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Learning conjunctions of Horn clauses

paper_content:

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable). The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula. >
---
paper_title: Exact Transversal Hypergraphs and Application to Boolean µ-Functions

paper_content:

Call an hypergraph, that is a family of subsets (edges) from a finite vertex set, an exact transversal hypergraph iff each of its minimal transversals, i.e., minimal vertex subsets that intersect each edge, meets each edge in a singleton. We show that such hypergraphs are recognizable in polynomial time and that their minimal transversals as well as their maximal independent sets can be generated in lexicographic order with polynomial delay between subsequent outputs, which is impossible in the general case unless P= NP. The results obtained are applied to monotone Boolean ?-functions, that are Boolean functions defined by a monotone Boolean expression (that is, built with ?, ? only) in which no variable occurs repeatedly. We also show that recognizing such functions from monotone Boolean expressions is co-NP-hard, thus complementing Mundici's result that this problem is in co-NP.
---
paper_title: On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions

paper_content:

Let f : {0,1} n → {0,1} be a monotone Boolean function whose value at any point x ∈ {0,1} n can be determined in time t. Denote by c=Λ I ∈ C ∨ i ∈ I x i the irredundant CNF off, where C is the set of the prime implicates of f. Similarly, let d=∨ J ∈ D Λ j ∈ J x j be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C' ⊆ C and D' ⊆ D such that (C',D') ¬= (C,D), a new term in (C\C')∪(D\D') can be found in time O(n(t+n))+m o(log m) , where m=|C'|+|D'|. In particular, if f(x) can be evaluated for every x ∈ {0,1} n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of Λ, ∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2 polylog(.) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D' =D or C' =C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of Λ, ∨-formulae of depth 3.
---
paper_title: On the frequency of the most frequently occurring variable in dual monotone DNFs

paper_content:

Abstract Let f ( X l ,…, X N )=⋁ I ∈ F ⋀ i ∈ I X i and g ( X l ,…, X N )=⋁ I ∈ G ⋀ i ∈ I X i be a pair of dual monotone irredundant disjunctive normal forms, where F and G are the sets of the prime implicants of tf and g , respectively. For a variable x i , i = 1, …, n , let μ i = # { I ∈ F | i ∈ I }/| F | and v i = # { I ∈ G | i ∈ I }/| G | be the frequencies with which x i occurs in f and g . It is easily seen that max { μ 1 , v 1 , …, μ n , v n } ⩾ 1/log(| F | + | G |). We give examples of arbitrarily large F and G for which the above bound is tight up to a factor of 2.
---
paper_title: Dual-Bounded Generating Problems: Partial And Multiple Transversals Of A Hypergraph

paper_content:

We consider two generalizations of the notion of transversal to a finite hypergraph, the so-called multiple and partial transversals. Multiple transversals naturally arise in 0-1 programming, while partial transversals are related to data mining and machine learning. We show that for an arbitrary hypergraph the families of multiple and partial transversals are both dual-bounded in the sense that the size of the corresponding dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal binary solutions for an arbitrary monotone system of linear inequalities.
---
paper_title: An intersection inequality for discrete distributions and related generation problems

paper_content:

Given two finite sets of points X, Y in Rn which can be separated by a nonnegative linear function, and such that the componentwise minimum of any two distinct points in X is dominated by some point in Y, we show that |X| = n|Y|. As a consequence of this result, we obtain quasi-polynomial time algorithms for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal empty hyper-rectangles for a given set of points in Rn. This provides a substantial improvement over previously known exponential algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, which, for the very special case of one inequality, implies that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
---
paper_title: Abduction and the Dualization Problem

paper_content:

Computing abductive explanations is an important problem, which has been studied extensively in Artificial Intelligence (AI) and related disciplines. While computing some abductive explanation for a literal χ with respect to a set of abducibles A from a Horn propositional theory Σ is intractable under the traditional representation of Σ by a set of Horn clauses, the problem is polynomial under model-based theory representation, where Σ is represented by its characteristic models. Furthermore, computing all the (possibly exponentially) many explanations is polynomial-time equivalent to the problem of dualizing a positive CNF, which is a well-known problem whose precise complexity in terms of the theory of NP-completeness is not known yet. In this paper, we first review the monotone dualization problem and its connection to computing all abductive explanations for a query literal and some related problems in knowledge discovery. We then investigate possible generalizations of this connection to abductive queries beyond literals. Among other results, we find that the equivalence for generating all explanations for a clause query (resp., term query) χ to the monotone dualization problem holds if χ contains at most k positive (resp., negative) literals for constant k, while the problem is not solvable in polynomial total-time, i.e., in time polynomial in the combined size of the input and the output, unless P=NP for general clause resp. term queries. Our results shed new light on the computational nature of abduction and Horn theories in particular, and might be interesting also for related problems, which remains to be explored.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Dual-Bounded Generating Problems: Weighted Transversals of a Hypergraph

paper_content:

Abstract We consider a generalization of the notion of transversal to a finite hypergraph, the so-called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of an input hypergraph A and a non-negative threshold vector, we define a weighted transversal as a minimal vertex set which intersects all the hyperedges of A except for a sub-family of total weight not exceeding the given threshold vector. Weighted transversals generalize partial and multiple transversals introduced in Boros et al. (SIAM J. Comput. 30 (6) (2001)) and also include minimal binary solutions to non-negative systems of linear inequalities and minimal weighted infrequent sets in databases. We show that the hypergraph of all weighted transversals is dual-bounded, i.e., the size of its transversal hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. For instance, we show that for any row-weighted m×n binary matrix and any threshold weight t, the number of maximal sets of columns whose row support has weight above t is at most m times the number of minimal sets of columns with row support of total weight below t. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal weighted infrequent sets of columns for a given binary matrix.
---
paper_title: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

paper_content:

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
---
paper_title: An inequality for polymatroid functions and its applications

paper_content:

An integral-valued set function f:2v ↦ Z is called polymatroid if it is submodular, nondecreasing, and f(φ) = 0. Given a polymatroid function f and an integer threshold t ≥ 1, let α = α(f,t) denote the number of maximal sets X ⊆ V satisfying f(X) < t, let β = β(f,t) be the number of minimal sets X ⊆ V for which f(X) ≥ t, and let n = |V|. We show that if β ≥ 2 then α ≤ β(log t)/c, where c = c(n,β) is the unique positive root of the equation 1 = 2c(nc/log β - 1). In particular, our bound implies that α ≤ (nβ)log t for all β ≥ 1. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α ≥ β(0.551 log t)/c. More generally, given a polymatroid function f : 2v ↦ Z and an integral threshold t ≥ 1, consider an arbitrary hypergraph H' such that |H'| ≥ 2 and f(H) ≥ t for all H ∈ H'. Let f' be the family of all maximal independent sets X of H' for which f(X) < t. Then |f'| ≤ |H'|(log t)/c(n,|H'|). As an application, we show that given a system of polymatroid inequalities f1(X) ≥ t1,..., fm(X) ≥ tm with quasi-polynomially bounded right-hand sides t1,....,tm, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.
---
paper_title: On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices

paper_content:

Given an m×n binary matrix A, a subset C of the columns is called t-frequent if there are at least t rows in A in which all entries belonging to C are non-zero. Let us denote by α the number of maximal t-frequent sets of A, and let β denote the number of those minimal column subsets of A which are not t-frequent (so called t-infrequent sets). We prove that the inequality α≤(m−t+1)β holds for any binary matrix A in which not all column subsets are t-frequent. This inequality is sharp, and allows for an incremental quasi-polynomial algorithm for generating all minimal t-infrequent sets. We also prove that the analogous generation problem for maximal t-frequent sets is NP-hard. Finally, we discuss the complexity of generating closed frequent sets and some other related problems.
---
paper_title: Generating Dual-Bounded Hypergraphs

paper_content:

This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and max...
---
paper_title: Dual-Bounded Generating Problems: Partial And Multiple Transversals Of A Hypergraph

paper_content:

We consider two generalizations of the notion of transversal to a finite hypergraph, the so-called multiple and partial transversals. Multiple transversals naturally arise in 0-1 programming, while partial transversals are related to data mining and machine learning. We show that for an arbitrary hypergraph the families of multiple and partial transversals are both dual-bounded in the sense that the size of the corresponding dual hypergraph is bounded by a polynomial in the cardinality and the length of description of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. We also show that the problems of generating all multiple and all partial transversals for a given hypergraph are polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known dualization problem for hypergraphs. As a corollary, we obtain incremental quasi-polynomial-time algorithms for both of the above problems, as well as for the generation of all the minimal binary solutions for an arbitrary monotone system of linear inequalities.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Dual-Bounded Generating Problems: Weighted Transversals of a Hypergraph

paper_content:

Abstract We consider a generalization of the notion of transversal to a finite hypergraph, the so-called weighted transversals. Given a non-negative weight vector assigned to each hyperedge of an input hypergraph A and a non-negative threshold vector, we define a weighted transversal as a minimal vertex set which intersects all the hyperedges of A except for a sub-family of total weight not exceeding the given threshold vector. Weighted transversals generalize partial and multiple transversals introduced in Boros et al. (SIAM J. Comput. 30 (6) (2001)) and also include minimal binary solutions to non-negative systems of linear inequalities and minimal weighted infrequent sets in databases. We show that the hypergraph of all weighted transversals is dual-bounded, i.e., the size of its transversal hypergraph is polynomial in the number of weighted transversals and the size of the input hypergraph. Our bounds are based on new inequalities of extremal set theory and threshold Boolean logic, which may be of independent interest. For instance, we show that for any row-weighted m×n binary matrix and any threshold weight t, the number of maximal sets of columns whose row support has weight above t is at most m times the number of minimal sets of columns with row support of total weight below t. We also prove that the problem of generating all weighted transversals for a given hypergraph is polynomial-time reducible to the generation of all ordinary transversals for another hypergraph, i.e., to the well-known hypergraph dualization problem. As a corollary, we obtain an incremental quasi-polynomial-time algorithm for generating all weighted transversals for a given hypergraph. This result includes as special cases the generation of all the minimal Boolean solutions to a given system of non-negative linear inequalities and the generation of all minimal weighted infrequent sets of columns for a given binary matrix.
---
paper_title: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

paper_content:

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
---
paper_title: An inequality for polymatroid functions and its applications

paper_content:

An integral-valued set function f:2v ↦ Z is called polymatroid if it is submodular, nondecreasing, and f(φ) = 0. Given a polymatroid function f and an integer threshold t ≥ 1, let α = α(f,t) denote the number of maximal sets X ⊆ V satisfying f(X) < t, let β = β(f,t) be the number of minimal sets X ⊆ V for which f(X) ≥ t, and let n = |V|. We show that if β ≥ 2 then α ≤ β(log t)/c, where c = c(n,β) is the unique positive root of the equation 1 = 2c(nc/log β - 1). In particular, our bound implies that α ≤ (nβ)log t for all β ≥ 1. We also give examples of polymatroid functions with arbitrarily large t, n, α and β for which α ≥ β(0.551 log t)/c. More generally, given a polymatroid function f : 2v ↦ Z and an integral threshold t ≥ 1, consider an arbitrary hypergraph H' such that |H'| ≥ 2 and f(H) ≥ t for all H ∈ H'. Let f' be the family of all maximal independent sets X of H' for which f(X) < t. Then |f'| ≤ |H'|(log t)/c(n,|H'|). As an application, we show that given a system of polymatroid inequalities f1(X) ≥ t1,..., fm(X) ≥ tm with quasi-polynomially bounded right-hand sides t1,....,tm, all minimal feasible solutions to this system can be generated in incremental quasi-polynomial time. In contrast to this result, the generation of all maximal infeasible sets is an NP-hard problem for many polymatroid inequalities of small range.
---
paper_title: On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices

paper_content:

Given an m×n binary matrix A, a subset C of the columns is called t-frequent if there are at least t rows in A in which all entries belonging to C are non-zero. Let us denote by α the number of maximal t-frequent sets of A, and let β denote the number of those minimal column subsets of A which are not t-frequent (so called t-infrequent sets). We prove that the inequality α≤(m−t+1)β holds for any binary matrix A in which not all column subsets are t-frequent. This inequality is sharp, and allows for an incremental quasi-polynomial algorithm for generating all minimal t-infrequent sets. We also prove that the analogous generation problem for maximal t-frequent sets is NP-hard. Finally, we discuss the complexity of generating closed frequent sets and some other related problems.
---
paper_title: Generating Dual-Bounded Hypergraphs

paper_content:

This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and max...
---
paper_title: New results on monotone dualization and generating hypergraph transversals

paper_content:

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by \chi(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.
---
paper_title: On Generating the Irredundant Conjunctive and Disjunctive Normal Forms of Monotone Boolean Functions

paper_content:

Let f : {0,1} n → {0,1} be a monotone Boolean function whose value at any point x ∈ {0,1} n can be determined in time t. Denote by c=Λ I ∈ C ∨ i ∈ I x i the irredundant CNF off, where C is the set of the prime implicates of f. Similarly, let d=∨ J ∈ D Λ j ∈ J x j be the irredundant DNF of the same function, where D is the set of the prime implicants of f. We show that given subsets C' ⊆ C and D' ⊆ D such that (C',D') ¬= (C,D), a new term in (C\C')∪(D\D') can be found in time O(n(t+n))+m o(log m) , where m=|C'|+|D'|. In particular, if f(x) can be evaluated for every x ∈ {0,1} n in polynomial time, then the forms c and d can be jointly generated in incremental quasi-polynomial time. On the other hand, even for the class of Λ, ∨-formulae f of depth 2, i.e., for CNFs or DNFs, it is unlikely that uniform sampling from within the set of the prime implicates and implicants of f can be carried out in time bounded by a quasi-polynomial 2 polylog(.) in the input size of f. We also show that for some classes of polynomial-time computable monotone Boolean functions it is NP-hard to test either of the conditions D' =D or C' =C. This provides evidence that for each of these classes neither conjunctive nor disjunctive irredundant normal forms can be generated in total (or incremental) quasi-polynomial time. Such classes of monotone Boolean functions naturally arise in game theory, networks and relay contact circuits, convex programming, and include a subset of Λ, ∨-formulae of depth 3.
---
paper_title: Complexity of Identification and Dualization of Positive Boolean Functions

paper_content:

Abstract We consider in this paper the problem of identifying min T(ƒ) and max F(ƒ) of a positive (i.e., monotone) Boolean function ƒ, by using membership queries only, where min T(ƒ) (max F(ƒ)) denotes the set of minimal true vectors (maximal false vectors) of ƒ. It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the existence of the following algorithms, where ƒ and g are positive Boolean functions: • An incrementally polynomial algorithm to dualize ƒ; • An incrementally polynomial algorithm to self-dualize ƒ; • A polynomial algorithm to decide if ƒ and are mutually dual; • A polynomial algorithm to decide if ƒ is self-dual; • A polynomial algorithm to decide if ƒ is saturated; • A polynomial algorithm in |min (ƒ)| + |max (ƒ)| to identify min (ƒ) only. Some of these are already well known open problems in the respective fields. Other related topics, including various equivalent problems encountered in hypergraph theory and theory of coteries (used in distributed systems), are also discussed.
---
paper_title: Identifying the Minimal Transversals of a Hypergraph and Related Problems

paper_content:

The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $\cal H$, decide if every subset of vertices is contained in or contains some edge of $\cal H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs ${\cal H}_{1}, {\cal H}_{2}$, decide if the sets in ${\cal H}_{2}$ are all the minimal transversals of ${\cal H}_{1}$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.
---
paper_title: An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

paper_content:

Given a finite set V , and a hypergraph H⊆ 2 V , the hyper- graph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practi- cal applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem (9). In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in (9), practical experience with this im- plementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in (9) can be used to give a stronger bound on the running time.
---
paper_title: Average Case Self-Duality of Monotone Boolean Functions

paper_content:

The problem of determining whether a monotone boolean function is self-dual has numerous applications in Logic and AI. The applications include theory revision, model-based diagnosis, abductive explanations and learning monotone boolean functions. It is not known whether self-duality of monotone boolean functions can be tested in polynomial time, though a quasi-polynomial time algorithm exists. We describe another quasi-polynomial time algorithm for solving the self-duality problem of monotone boolean functions and analyze its average-case behaviour on a set of randomly generated instances.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Almost all monotone Boolean functions are polynomially learnable using membership queries

paper_content:

We consider exact learning or identification of monotone Boolean functions by only using membership queries. It is shown that almost all monotone Boolean functions are polynomially identifiable in the input number of variables as well as the output being the sum of the sizes of the CNF and DNF representations.
---
paper_title: Complexity of Identification and Dualization of Positive Boolean Functions

paper_content:

Abstract We consider in this paper the problem of identifying min T(ƒ) and max F(ƒ) of a positive (i.e., monotone) Boolean function ƒ, by using membership queries only, where min T(ƒ) (max F(ƒ)) denotes the set of minimal true vectors (maximal false vectors) of ƒ. It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the existence of the following algorithms, where ƒ and g are positive Boolean functions: • An incrementally polynomial algorithm to dualize ƒ; • An incrementally polynomial algorithm to self-dualize ƒ; • A polynomial algorithm to decide if ƒ and are mutually dual; • A polynomial algorithm to decide if ƒ is self-dual; • A polynomial algorithm to decide if ƒ is saturated; • A polynomial algorithm in |min (ƒ)| + |max (ƒ)| to identify min (ƒ) only. Some of these are already well known open problems in the respective fields. Other related topics, including various equivalent problems encountered in hypergraph theory and theory of coteries (used in distributed systems), are also discussed.
---
paper_title: An intersection inequality for discrete distributions and related generation problems

paper_content:

Given two finite sets of points X, Y in Rn which can be separated by a nonnegative linear function, and such that the componentwise minimum of any two distinct points in X is dominated by some point in Y, we show that |X| = n|Y|. As a consequence of this result, we obtain quasi-polynomial time algorithms for generating all maximal integer feasible solutions for a given monotone system of separable inequalities, for generating all p-inefficient points of a given discrete probability distribution, and for generating all maximal empty hyper-rectangles for a given set of points in Rn. This provides a substantial improvement over previously known exponential algorithms for these generation problems related to Integer and Stochastic Programming, and Data Mining. Furthermore, we give an incremental polynomial time generation algorithm for monotone systems with fixed number of separable inequalities, which, for the very special case of one inequality, implies that for discrete probability distributions with independent coordinates, both p-efficient and p-inefficient points can be separately generated in incremental polynomial time.
---
paper_title: Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

paper_content:

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.
---
paper_title: Generating Dual-Bounded Hypergraphs

paper_content:

This article surveys some recent results on the generation of implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and combinatorics. Given a monotone property ~ over the subsets of a finite set V, we consider the problem of incrementally generating the family F π of all minimal subsets satisfying property ~ , when ~ is given by a polynomial-time satisfiability oracle. For a number of interesting monotone properties, the family F π turns out to be uniformly dual-bounded , allowing for the incrementally efficient enumeration of the members of F π. Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and max...
---
paper_title: On dualization in products of forests, in

paper_content:

Let P = P 1 × … x P n be the product of n partially ordered sets, each with an acyclic precedence graph in which either the in-degree or the out-degree of each element is bounded. Given a subset A C P, it is shown that the set of maximal independent elements of A in P can be incrementally generated in quasi-polynomial time. We discuss some applications in data mining related to this dualization problem.
---
paper_title: On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions

paper_content:

Abstract A criterion of the optimality of an algorithm for evaluating monotonic Boolean functions, which is different from the Shannon criterion, is considered and its practical significance is proved. Upper and lower estimates are obtained for the efficiency of the algorithm for evaluating monotonic Boolean functions which is optimal with respect to the criterion which has been introduced. An algorithm is constructed for evaluating the class of monotonic Boolean functions which are generated by imcompatible systems of linear ineaqualities. This algorithm is optimal with respect to the criterion introduced in this paper, the Shannon criterion, and a number of other criteria subject to certain additional conditions.
---
paper_title: A fast parallel algorithm for the maximal independent set problem

paper_content:

A parallel algorithm is presented which accepts as input a graph G and produces a maximal independent set of vertices in G. On a P-RAM without the concurrent write or concurrent read features, the algorithm executes in O((log n) 4 ) time and uses O((n/log n) 3 ) processors, where n is the number of vertices in G. The algorithm has several novel features that may find other applications. These include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a “dynamic pigeonhole principle” that generalizes the conventional pigeonhole principle.
---
paper_title: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms

paper_content:

Suppose that an independence system $(E,\mathcal {I})$ is characterized by a subroutine which indicates in unit time whether or not a given subset of E is independent. It is shown that there is no algorithm for generating all the K maximal independent sets of such an independence system in time polynomial in $|E|$ and K, unless $\mathcal {P} = \mathcal {NP}$. However, it is possible to apply ideas of Paull and Unger and of Tsukiyama et al. to obtain polynomial-time algorithms for a number of special cases, e.g. the efficient generation of all maximal feasible solutions to a knapsack problem. The algorithmic techniques bear an interesting relationship with those of Read for the enumeration of graphs and other combinatorial configurations.
---
paper_title: A New Algorithm for the Hypergraph Transversal Problem

paper_content:

We consider the problem of finding all minimal transversals of a hypergraph ${\mathcal H}\subseteq 2^V$, given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hypergraphs, e.g. hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of ${\mathcal H}$ in time bounded by ${\rm polylog}(|V|,|{\mathcal H}|,k)$ assuming ${\rm poly}(|V|,|{\mathcal H}|,k)$ number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii) Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.
---
paper_title: A variant of Reiter's hitting-set algorithm

paper_content:

In this paper we introduce a variant of Reiter's hitting-set algorithm. This variant produces a hitting-set tree instead of an acyclic directed graph. As an advantage some subset checks necessary for reducing the graph during search can be avoided.
---
paper_title: Hypergraph Transversal Computation and Related Problems in Logic and AI

paper_content:

Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional variant, i.e., the recognition of the transversal hypergraph for another hypergraph. We survey some results on problems which are known to be related to computing the transversal hypergraph, where we focus on problems in propositional Logic and AI. Some of the results have been established already some time ago, and were announced but their derivation was not widely disseminated. We then address recent developments on the computational complexity of computing resp. recognizing the transversal hypergraph. The precise complexity of these problems is not known to date, and is in fact open for more than 20 years now.
---
paper_title: Queries and Concept Learning

paper_content:

We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.
---
paper_title: An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension

paper_content:

We show that for hypergraphs of bounded edge size, the problem of extending a given list of maximal independent sets is NC-reducible to the computation of an arbitrary maximal independent set for an induced sub-hypergraph. The latter problem is known to be in RNC. In particular, our reduction yields an incremental RNC dualization algorithm for hypergraphs of bounded edge size, a problem previously known to be solvable in polynomial incremental time. We also give a similar parallel algorithm for the dualization problem on the product of arbitrary lattices which have a bounded number of immediate predecessors for each element.
---
paper_title: Almost all monotone Boolean functions are polynomially learnable using membership queries

paper_content:

We consider exact learning or identification of monotone Boolean functions by only using membership queries. It is shown that almost all monotone Boolean functions are polynomially identifiable in the input number of variables as well as the output being the sum of the sizes of the CNF and DNF representations.
---
paper_title: The computation of hitting sets: review and new algorithms

paper_content:

In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.
---
paper_title: A Correction to the Algorithm in Reiter's Theory of Diagnosis

paper_content:

Reiter [3] has developed a general theory of diagnosis based on first principles. His algorithm computes all diagnoses which explain the differences between the predicted and observed behavior of a given system. Unfortunately, Reiter's description of the algorithm is incorrect in that some diagnoses can be missed under certain conditions. This note presents a revised algorithm and a proof of its correctness.
---
paper_title: Polynomial Time Recognition Of 2-Monotonic Positive Boolean Functions Given By An Oracle

paper_content:

We consider the problem of identifying an unknown Boolean function $f$ by asking an oracle the functional values $f(a)$ for a selected set of test vectors $a \in \{0,1\}^{n}$. Furthermore, we assume that $f$ is a positive (or monotone) function of $n$ variables. It is not yet known whether or not the whole task of generating test vectors and checking if the identification is completed can be carried out in polynomial time in $n$ and $m$, where $m=|\min T(f)| + |\max F(f)|$ and $\min T(f)$ (respectively, $\max F(f))$ denotes the set of minimal true (respectively, maximal false) vectors of $f$. To partially answer this question, we propose here two polynomial-time algorithms that, given an unknown positive function $f$ of $n$ variables, decide whether or not $f$ is 2-monotonic and, if $f$ is 2-monotonic, output both sets $\min T(f)$ and $\max F(f)$. The first algorithm uses $O(nm^{2} + n^{2}m)$ time and $O(nm)$ queries, while the second one uses $O(n^{3}m)$ time and $O(n^{3}m)$ queries.
---
paper_title: A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

paper_content:

Consider the problem of identifying minT(f) and maxF(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where minT(f) (maxF(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both minT(f) and maxF(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n2m) time andO(n2m) queries, wherem=|minT(f)|+|maxF(f)|. This answers affirmatively the conjecture raised in Boroset al.Lecture Notes in Comput. Sci.557(1991), 104?115, Boroset al.SIAM J. Comput.26(1997), 93?109, and is an improvement over the two algorithms discussed therein: one usesO(n3m) time andO(n3m) queries, and the other usesO(nm2+n2m) time andO(nm) queries.
---
paper_title: Data mining, hypergraph transversals, and machine learning

paper_content:

Several data mining problems can be formulated as problems of finding maximally specific sentences that are interesting in a database. We first show that this problem has a close relationship with the hypergraph transversal problem. We then analyze two algorithms that have been previously used in data mining, proving upper bounds on their complexity. The first algorithm is useful when the maximally specific interesting sentences are “small”. We show that this algorithm can also be used to efficiently solve a special case of the hypergraph transversal problem, improving on previous results. The second algorithm utilizes a subroutine for hypergraph transversals, and is applicable in more general situations, with complexity close to a lower bound for the problem. We also relate these problems to the model of exact learning in computational learning theory, and use the correspondence to derive some corollaries.
---
paper_title: Algorithms for inferring functional dependencies from relations

paper_content:

Abstract The dependency inference problem is to find a cover of the set of functional dependencies that hold in a given relation. The problem has applications in relational database design, in query optimization, and in artificial intelligence. The problem is exponential in the number of attributes. We develop two algorithms with better best case behavior than the simple one. One algorithm reduces the problem to computing the transversal of a hypergraph. The other is based on repeatedly sorting the relation with respect to a set of attributes.
---
paper_title: New results on monotone dualization and generating hypergraph transversals

paper_content:

We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by \chi(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.
---
paper_title: The Maximum Latency and Identification of Positive Boolean Functions

paper_content:

Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean function f, by using membership queries only, where min T(f) (maxF(f)) denotes the set of minimal true vectors (maximal false vectors) of f. It is known that an incrementally polynomial algorithm exists if and only if there is a polynomial time algorithm to check the existence of an unknown vector for given sets MT\(\subseteq \) min T(f) and MF\(\subseteq \) max F(f). Unfortunately, however, the complexity of this problem is still unknown. To answer this question partially, we introduce in this paper a measure for the difficulty of finding an unknown vector, which is called the maximum latency. If the maximum latency is constant, then an unknown vector can be found in polynomial time and there is an incrementally polynomial algorithm for identification. Several subclasses of positive functions are shown to have constant maximum latency, e.g., 2-monotonic positive functions, Δ-partial positive threshold functions and matroid functions, while the class of general positive functions has maximum latency not smaller than [n/4]+1 and the class of positive k-DNF functions has Ω(√n) maximum latency.
---
paper_title: Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections

paper_content:

Given a finite set V, and integers k > 1 and r > 0, denote by A(k, r) the class of hypergraphs A ⊆ 2 V with (k, r)-bounded intersections, i.e. in which the intersection of any k distinct hyperedges has size at most r. We consider the problem MIS(A,I): given a hypergraph A and a subfamily I C I(A), of its maximal independent sets (MIS) I(A), either extend this subfamily by constructing a new MIS I ∈ I(A) \ I or prove that there are no more MIS, that is I = I(A). We show that for hypergraphs A E A(k,r) with k + r ≤ const, problem MIS(A,I) is NC-reducible to problem MIS(A',O) of generating a single MIS for a partial subhypergraph A' of A. In particular, for this class of hypergraphs, we get an incremental polynomial algorithm for generating all MIS. Furthermore, combining this result with the currently known algorithms for finding a single maximal independent set of a hypergraph, we obtain efficient parallel algorithms for incrementally generating all MIS for hypergraphs in the classes A(1, c), A(c, 0), and A(2,1), where c is a constant. We also show that, for A ∈ A(k,r), where k + r < const, the problem of generating all MIS of A can be solved in incremental polynomial-time with space polynomial only in the size of A.
---
paper_title: Exact Learning of Subclasses of CDNF Formulas with Membership Queries

paper_content:

We consider the exact, learuability of subclasses of Boolean formulas from membership queries alone. We show how to combine known learning algorithms that use membership and equivalence queries to obtain new learning results only with memberships. In particular we show the exact learuability of read-k monotone formulas, Sat-k\(\mathcal{O}\)(log n)-CDNF, and \(\mathcal{O}(\sqrt {\log n} )\)-size CDNF from membership queries only.
---
paper_title: A theory of the learnable

paper_content:

Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.
---
paper_title: Complexity of Identification and Dualization of Positive Boolean Functions

paper_content:

Abstract We consider in this paper the problem of identifying min T(ƒ) and max F(ƒ) of a positive (i.e., monotone) Boolean function ƒ, by using membership queries only, where min T(ƒ) (max F(ƒ)) denotes the set of minimal true vectors (maximal false vectors) of ƒ. It is shown that the existence of an incrementally polynomial algorithm for this problem is equivalent to the existence of the following algorithms, where ƒ and g are positive Boolean functions: • An incrementally polynomial algorithm to dualize ƒ; • An incrementally polynomial algorithm to self-dualize ƒ; • A polynomial algorithm to decide if ƒ and are mutually dual; • A polynomial algorithm to decide if ƒ is self-dual; • A polynomial algorithm to decide if ƒ is saturated; • A polynomial algorithm in |min (ƒ)| + |max (ƒ)| to identify min (ƒ) only. Some of these are already well known open problems in the respective fields. Other related topics, including various equivalent problems encountered in hypergraph theory and theory of coteries (used in distributed systems), are also discussed.
---
paper_title: Efficient Read-Restricted Monotone CNF/DNF Dualization by Learning with Membership Queries

paper_content:

We consider exact learning monotone CNF formulas in which each variable appears at most some constant k times (“read-k” monotone CNF). Let f : l0,1r^n → l0,1r be expressible as a read-k monotone CNF formula for some natural number k. We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and (not necessarily read restricted) DNF descriptions of f. The algorithm‘s only method of obtaining information about f is through membership queries, i.e., by inquiring about the value f(x) for points x ∈ l0,1r^n. The algorithm yields an incremental polynomial output time solution to the (read-k) monotone CNF/DNF dualization problem. The unrestricted versions remain open problems of importance.
---
paper_title: On one criterion of the optimality of an algorithm for evaluating monotonic Boolean functions

paper_content:

Abstract A criterion of the optimality of an algorithm for evaluating monotonic Boolean functions, which is different from the Shannon criterion, is considered and its practical significance is proved. Upper and lower estimates are obtained for the efficiency of the algorithm for evaluating monotonic Boolean functions which is optimal with respect to the criterion which has been introduced. An algorithm is constructed for evaluating the class of monotonic Boolean functions which are generated by imcompatible systems of linear ineaqualities. This algorithm is optimal with respect to the criterion introduced in this paper, the Shannon criterion, and a number of other criteria subject to certain additional conditions.
---
paper_title: An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

paper_content:

Given a finite set V , and a hypergraph H⊆ 2 V , the hyper- graph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practi- cal applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem (9). In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in (9), practical experience with this im- plementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in (9) can be used to give a stronger bound on the running time.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: Detailed Description of an Algorithm for Enumeration of Maximal Frequent Sets with Irredundant Dualization

paper_content:

We describe an implementation of an algorithm for enumerating all maximal frequent sets using irredundant dualization, which is an improved version of that of Gunopulos et al. The algorithm of Gunopulos et al. solves many dualization problems, and takes long computation time. We interleaves dualization with the main algorithm, and reduce the computation time for dualization by as long as one dualization. This also reduces the space complexity. Moreover, we accelerate the computation by using sparseness.
---
paper_title: An Efficient Algorithm for the Transversal Hypergraph Generation

paper_content:

The Transversal Hypergraph Generation is the problem of generating, given a hypergraph, the set of its minimal transversals, i.e., the hypergraph whose hyperedges are the minimal hitting sets of the given one. The purpose of this paper is to present an efficient and practical algorithm for solving this problem. We show that the proposed algorithm operates in a way that rules out regeneration and, thus, its memory requirements are polynomially bounded to the size of the input hypergraph. Although no time bound for the algorithm is given, experimental evaluation and comparison with other approaches have shown that it behaves well in practice and it can successfully handle large problem instances.
---
paper_title: Evaluation of an Algorithm for the Transversal Hypergraph Problem

paper_content:

The Transversal Hypergraph Problem is the problem of computing, given a hypergraph, the set of its minimal transversals, i.e. the hypergraph whose hyperedges are all minimal hitting sets of the given one. This problem turns out to be central in various fields of Computer Science. We present and experimentally evaluate a heuristic algorithm for the problem, which seems able to handle large instances and also possesses some nice features especially desirable in problems with large output such as the Transversal Hypergraph Problem.
---
paper_title: Minimizing the Average Query Complexity of Learning Monotone Boolean Functions

paper_content:

This paper addresses the problem of completely reconstructing deterministic monotone Boolean functions via membership queries. The minimum average query complexity is guaranteed via recursion, where partially ordered sets (posets) make up the overlapping subproblems. For problems with up to 4 variables, the posets' optimality conditions are summarized in the form of an evaluative criterion. The evaluative criterion extends then computational feasibility to problems involving up to about 20 variables. A frameworkfor unbiased average case comparison of monotone Boolean function inference algorithms is developed using unequal probability sampling. The unbiased empirical results show that an implementation of the subroutine considered as a standard in the literature performs almost twice as many queries as the evaluative criterion on the average. It should also be noted that the first algorithm ever designed for this problem performed consistently within two percentage points of the evaluative criterion. As such, it prevails, by far, as the most efficient of the many preexisting algorithms.
---
paper_title: The computation of hitting sets: review and new algorithms

paper_content:

In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.
---
paper_title: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns

paper_content:

Computing the minimal transversals of a hypergraph is an important problem in computer science that has significant applications in data mining. We present a new algorithm for computing hypergraph transversals and highlight their close connection to an important class of patterns known as emerging patterns. We evaluate our technique on a number of large datasets and show that it outperforms previous approaches by a factor of 9-29 times.
---
paper_title: A Practical Fast Algorithm for Enumerating Minimal SetCoverings

paper_content:

For a set family F defined on a grand set E, a subset of F covering all the elements of E is called a set covering. The enumeration problem of minimal set covering is equal to the enumeration problem of hypergraph dualization, minimal hitting sets, and other other many problems, and have been studied intensively. However, the existence of an output polynomial algorithm for this problem is still open. However, there proposed an algorithm whose average computation time on computational experiments for random generated instances is output polynomial. In this paper, we propose a practical fast algorithm obtained by improving this algorithm, and by computational experiments, show that the average computation time for randomly generated instances is O(|E|) per output, by computational experiments.
---
paper_title: Bidual Horn Functions and Extensions

paper_content:

Partially defined Boolean functions (pdBf) , where are disjoint sets of true and false vectors, generalize total Boolean functions by allowing that the function values on some input vectors are unknown. The main issue with pdBfs is the extension problem, which is deciding, given a pdBf, whether it is interpolated by a function from a given class of total Boolean functions, and computing a formula for . In this paper, we consider extensions of bidual Horn functions, which are the Boolean functions such that both and its dual function are Horn. They are intuitively appealing for considering extensions because they give a symmetric role to positive and negative information (i.e., true and false vectors) of a pdBf, which is not possible with arbitrary Horn functions. Bidual Horn functions turn out to constitute an intermediate class between positive and Horn functions which retains several benign properties of positive functions. Besides the extension problem, we study recognition of bidual Horn functions from Boolean formulas and properties of normal form expressions. We show that finding a bidual Horn extension and checking biduality of a Horn DNF is feasible in polynomial time, and that the latter is intractable from arbitrary formulas. We also give characterizations of shortest DNF expressions of a bidual Horn function and show how to compute such an expression from a Horn DNF for in polynomial time; for arbitrary Horn functions, this is NP-hard. Furthermore, we show that a polynomial total algorithm for dualizing a bidual Horn function exists if and only if there is such an algorithm for dualizing a positive function.
---
paper_title: Translating between Horn Representations and their Characteristic Models

paper_content:

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.
---
paper_title: An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals

paper_content:

Given a finite set V , and a hypergraph H⊆ 2 V , the hyper- graph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practi- cal applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan (1996) gave an incremental quasi-polynomial time algorithm for solving the hypergraph transversal problem (9). In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same bound on the running time as in (9), practical experience with this im- plementation shows that it can be substantially faster. We also show that a slight modification of the algorithm in (9) can be used to give a stronger bound on the running time.
---
paper_title: On the Complexity of Dualization of Monotone Disjunctive Normal Forms

paper_content:

We show that the duality of a pair of monotone disjunctive normal forms of sizencan be tested inno(logn)time.
---
paper_title: A New Algorithm for the Hypergraph Transversal Problem

paper_content:

We consider the problem of finding all minimal transversals of a hypergraph ${\mathcal H}\subseteq 2^V$, given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hypergraphs, e.g. hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of ${\mathcal H}$ in time bounded by ${\rm polylog}(|V|,|{\mathcal H}|,k)$ assuming ${\rm poly}(|V|,|{\mathcal H}|,k)$ number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii) Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.
---
paper_title: Detailed Description of an Algorithm for Enumeration of Maximal Frequent Sets with Irredundant Dualization

paper_content:

We describe an implementation of an algorithm for enumerating all maximal frequent sets using irredundant dualization, which is an improved version of that of Gunopulos et al. The algorithm of Gunopulos et al. solves many dualization problems, and takes long computation time. We interleaves dualization with the main algorithm, and reduce the computation time for dualization by as long as one dualization. This also reduces the space complexity. Moreover, we accelerate the computation by using sparseness.
---
paper_title: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction

paper_content:

We study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (Actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (FPT) results.) Two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. In particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most k elements. As an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology.
---
paper_title: Evaluation of an Algorithm for the Transversal Hypergraph Problem

paper_content:

The Transversal Hypergraph Problem is the problem of computing, given a hypergraph, the set of its minimal transversals, i.e. the hypergraph whose hyperedges are all minimal hitting sets of the given one. This problem turns out to be central in various fields of Computer Science. We present and experimentally evaluate a heuristic algorithm for the problem, which seems able to handle large instances and also possesses some nice features especially desirable in problems with large output such as the Transversal Hypergraph Problem.
---
paper_title: Minimizing the Average Query Complexity of Learning Monotone Boolean Functions

paper_content:

This paper addresses the problem of completely reconstructing deterministic monotone Boolean functions via membership queries. The minimum average query complexity is guaranteed via recursion, where partially ordered sets (posets) make up the overlapping subproblems. For problems with up to 4 variables, the posets' optimality conditions are summarized in the form of an evaluative criterion. The evaluative criterion extends then computational feasibility to problems involving up to about 20 variables. A frameworkfor unbiased average case comparison of monotone Boolean function inference algorithms is developed using unequal probability sampling. The unbiased empirical results show that an implementation of the subroutine considered as a standard in the literature performs almost twice as many queries as the evaluative criterion on the average. It should also be noted that the first algorithm ever designed for this problem performed consistently within two percentage points of the evaluative criterion. As such, it prevails, by far, as the most efficient of the many preexisting algorithms.
---
paper_title: The computation of hitting sets: review and new algorithms

paper_content:

In model-based diagnosis or other research fields, the hitting sets of a set cluster are usually used. In this paper we introduce some algorithms, including the new BHS-tree and Boolean algebraic algorithms. In the BHS-tree algorithm, a binary-tree is used for the computation of hitting sets, and in the Boolean algebraic algorithm, components are represented by Boolean variables. It runs just for one time to catch the minimal hitting sets. We implemented the algorithms and present empirical results in order to show their superiority over other algorithms for computing hitting sets.
---
paper_title: New Algorithms for Enumerating All Maximal Cliques

paper_content:

In this paper, we consider the problems of generating all maximal (bipartite) cliques in a given (bipartite) graph G=(V,E) with n vertices and m edges. We propose two algorithms for enumerating all maximal cliques. One runs with O(M(n)) time delay and in O(n 2) space and the other runs with O(Δ4) time delay and in O(n+m) space, where Δ denotes the maximum degree of G, M(n) denotes the time needed to multiply two n × n matrices, and the latter one requires O(nm) time as a preprocessing.
---
paper_title: A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns

paper_content:

Computing the minimal transversals of a hypergraph is an important problem in computer science that has significant applications in data mining. We present a new algorithm for computing hypergraph transversals and highlight their close connection to an important class of patterns known as emerging patterns. We evaluate our technique on a number of large datasets and show that it outperforms previous approaches by a factor of 9-29 times.
---

Title: COMPUTATIONAL ASPECTS OF MONOTONE DUALIZATION: A BRIEF SURVEY

Section 1: Introduction
Description 1: Introduce the monotone dualization problem, its significance, historical context, and application areas.

Section 2: Preliminaries
Description 2: Provide basic definitions and concepts related to Boolean functions, CNF, DNF, and their properties necessary for understanding monotone dualization.

Section 3: Simple Algorithms
Description 3: Discuss basic algorithms for dualization, including clause-based and variable-based decomposition methods, and their limitations.

Section 4: Fredman and Khachiyan's Results
Description 4: Detail the seminal results by Fredman and Khachiyan, their algorithms A and B, and the theoretical implications of their work on the complexity of the dualization problem.

Section 5: Follow-Up Work
Description 5: Summarize the subsequent research influenced by Fredman and Khachiyan's work, focusing on different computational aspects, limited nondeterminism, and probabilistic approaches.

Section 6: Generalizations to Posets
Description 6: Explain extensions of the dualization problem to partially ordered sets (posets) and the associated computational challenges and results.

Section 7: Other Algorithms
Description 7: Cover various alternative algorithms for dualization, including those based on learning theory, partitioning methods, and parallel computation.

Section 8: Implementations and Experiments
Description 8: Review practical implementations and experimental evaluations of dualization algorithms, discussing performance aspects and comparative studies.

Section 9: Discussion and Conclusion
Description 9: Conclude with a discussion on open problems, future research directions, and a summary of the state of the art in the computational aspects of monotone dualization.