Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.

Given a Boolean function f, we define the importance of a set S of variables by an expression measuring to what extent the variables in S determine the value of f. This "evaluation" uses a "constancy" measure which is assumed to be a real-valued convex function defined on [0,1]. In spite of the generality of the constancy measure, it is shown that any such evaluation is in strong agreement with the classical concept of the Winder-strength of variables of a monotone Boolean function. Further, we study a special class of evaluations called relevances, characterize completely the cases of extreme relevance value, relating the sets of maximum relevance to fictitious (dummy) variables and support sets, and establish a lower bound on the relevance of sets "containing" implicants or implicates of a Boolean function.

Describes a new, logic-based methodology for analyzing observations. The key features of this “logical analysis of data” (LAD) methodology are the discovery of minimal sets of features that are necessary for explaining all observations and the detection of hidden patterns in the data that are capable of distinguishing observations describing “positive” outcome events from “negative” outcome events. Combinations of such patterns are used for developing general classification procedures. An implementation of this methodology is described in this paper, along with the results of numerical experiments demonstrating the classification performance of LAD in comparison with the reported results of other procedures. In the final section, we describe three pilot studies on applications of LAD to oil exploration, psychometric testing and the analysis of developments in the Chinese transitional economy. These pilot studies demonstrate not only the classification power of LAD but also its flexibility and capability to provide solutions to various case-dependent problems.

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.

Horn knowledge bases are widely used in many applications. The paper is concerned with the optimal compression of propositional Horn production rule bases-one of the most important knowledge bases used in practice. The problem of knowledge compression is interpreted as a problem of Boolean function minimization. It was proved by P.L. Hammer and A. Kogan (1993) that the minimization of Horn functions, i.e., Boolean functions associated with Horn knowledge bases, is NP complete. The paper deals with the minimization of quasi acyclic Horn functions, the class of which properly includes the two practically significant classes of quadratic and of acyclic functions. A procedure is developed for recognizing in quadratic time the quasi acyclicity of a function given by a Horn CNF, and a graph based algorithm is proposed for the quadratic time minimization of quasi acyclic Horn functions.>

This paper associates a linear programming problem (LP) to any conjunctive normal form $\phi $, and shows that the optimum value $Z(\phi )$ of this LP measures the complexity of the corresponding ${\textit{SAT}}$ (Boolean satisfiability) problem. More precisely, there is an algorithm for ${\textit{SAT}}$ that runs in polynomial time on the class of satisfiability problems satisfying $Z(\phi ) \leqslant 1 + \tfrac{{c\log n}}{n}$ for a fixed constant c, where c is the number of variables. In contrast, for any fixed $\beta < 1$, $SAT$ is still NP complete when restricted to the class of CNFs for which $Z(\phi ) \leqslant 1 + ({1 / {n^\beta }})$.

This paper addresses a prediction problem occurring frequently in practice. The problem consists in predicting the value of a function on the basis of discrete observational data that are incomplete in two senses. Only certain arguments of the function are observed, and the function value is observed only for certain combinations of values of these arguments. The problem is considered under a monotonicity condition that is natural in many applications. Applications to tax auditing, medicine, and real estate valuation are discussed. In particular, a special class of problems is identified for which the best monotone prediction can be found in polynomial time.

In this paper a new lower bound for unconstrained quadratic 0 – 1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron ${\text{S}}^{[3]} $, defined by the constraints of this LP formulation is precisely the first Chvátal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with ${\text{S}}^{[3]} $. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.

Data flow machines whose task graphs are acyclic can be transformed into synchronous machines, thereby increasing pipelining and throughput. This is achieved by introducing delays or buffers on certain lines, so that the resulting graph is balanced, i.e., travel times along any two paths with common endpoints are the same. The buffer assignment problem is how to balance a rooted acyclic data flow graph with a minimum number of buffer units. Recently, an integer programming decomposition procedure was proposed for this problem. The decomposition was introduced in an attempt to circumvent the exponential blowup typical of integer programming algorithms. It is shown that the buffer assignment problem can in fact be solved to optimality in low-degree polynomial time. The result is obtained by a sequence of reformulations of the problem, leading to models to which simple and efficient network flow procedures can be successfully applied.>

Abstract A 2‐threshold graph is defined to be the edge‐union of two threshold graphs. We prove that all chordless cycles of size at least 5 and their complements are forbidden for 2‐threshold graphs. We also obtain a sufficient condition for a 2‐threshold graph to be a comparability graph. Finally, we show that 2‐threshold graphs can have at most three cutpoints and obtain efficient algorithms to recognize, decompose and obtain a maximum stable set of 2‐threshold graphs with exactly three cutpoints.

When an injective pseudo-Boolean function $f:B^n \to \mathbb{R}$ is minimized, where $B^n = \{ 0,1 \}^n$ is the set of vertices of the unit-hypercube, it is natural to consider so-called greedy vertex-following algorithms. These algorithms construct a sequence of neighbouring (Hamming distance 1) vertices with decreasing f-value. The question arises as to when such algorithms will find the global optimum given any starting point. This paper describes a hierarchy of such classes of functions that are shown to strictly contain each other. These classes are, in increasing order of generality, the threshold, the saddle-free, the pseudomodular, the completely unimodal, the unimodal, and the unimin (respectively, unimax) functions. Some considerations as to the complexity of the above-mentioned class of algorithms are also made.

Given a monotone (nondecreasing) switching function F(x1,···,xn), its prime implicants are the minimal infeasible points, i.e., the minimal solutions to F(x) = 1. A monotone F is regular ifany "right shift" of a feasible point is again feasible. The roofs of a regular function F are those prime implicants al ofwhose right shifts are feasible. The set of these roofs completely determines F. An algorithm is presented to compute the roofs of the dual Boolean function Fd= F̄(x̄) This computation is needed, for example, in the synthesis problem ofthreshold logic. The algorithm "scans" all the 2npoints in lexicographical order, skipping over intervals which are clearly roof-free. The amount of this work is proportional to the number of prime implicants of F. Encouraging computational experience is reported.

A branch-and-bound method is proposed for the maximization of real valued functions with variables assuming only the values 0 and 1.The importance of the problem consists-as has been shown by Hammer and Rudeanu-in the fact that numerous problems in operations research, graph theory, combinatorial mathematics, etc., can be brought to this form.The method has been successfully tested on an IBM 360/50 computer.