Dualization of boolean functions using ternary decision diagrams

Dualization of Boolean functions is a fundamental problem that appears in various fields such as artificial intelligence, logic, data mining, etc. For monotone Boolean functions, many empirical researches that focus on practical efficiency have recently been done. We extend our previous work for monotone dualization and present a novel method for dualization that allows us to handle any Boolean function, including non-monotone Boolean functions. We furthermore present a variant of this method in cooperation with all solutions solver. By experiments we evaluate efficiency and characteristics of our methods.     

Dualization, decision lists and identification of monotone discrete functions

Many data-analysis algorithms in machine learning, datamining and a variety of other disciplines essentially operate on discrete multi-attribute data sets. By means of discretisation or binarization also numerical data sets can be successfully analysed. Therefore, in this paper we view/introduce the theory of (partially defined) discrete functions as an important theoretical tool for the analysis of multi-attribute data sets. In particular we study monotone (partially defined) discrete functions. Compared with the theory of Boolean functions relatively little is known about (partially defined) monotone discrete functions. It appears that decision lists are useful for the representation of monotone discrete functions. Since dualization is an important tool in the theory of (monotone) Boolean functions, we study the interpretation and properties of the dual of a (monotone) binary or discrete function. We also introduce the dual of a pseudo-Boolean function. The results are used to investigate extensions of partially defined monotone discrete functions and the identification of monotone discrete functions. In particular, we present a polynomial time algorithm for the identification of so-called stable discrete functions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Proof of two conjectures on correlation inequalities for one class of monotone functions

We prove two correlation inequalities conjectured in [1] for functions that are linear combinations of unimodal Boolean monotone nondecreasing functions.     

A characterization of span program size and improved lower bounds for monotone span programs

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.?In the monotone case our new methods yield lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is suficient for constructing Boolean functions with large monotone span program complexity. Received: September 30, 2000.     

Limiting negations in bounded-depth circuits: An extension of Markov's theorem

A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration.     

Exact Transversal Hypergraphs and Application to Boolean μ-Functions

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.     

A counterexample to a conjecture of Schnorr referring to monotone networks

Schnorr[1] proved a lower bound on the number of additions in monotone computations of rational polynomials. He conjectured a similar lower bound on the number of ∨-gates in monotone networks computing monotone Boolean functions. We disprove this conjecture.     

The complexity of monotone boolean functions

We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function ofn arguments is less by the factor (2/n)^1/2, where is the circular ratio, than the complexity of realizing an arbitrary Boolean function ofn arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines.     

A new lower bound on the monotone network complexity of Boolean sums

Summary Neciporuk [3], Lamagna/Savage [1] and Tarjan [6] determined the monotone network complexity of a set of Boolean sums if each two sums have at most one variable in common. By this result they could define explicitely a set of n Boolean sums which depend on n variables and whose monotone complexity is of order n ^3/2. In the main theorem of this paper we prove a more general lower bound on the monotone network complexity of Boolean sums. Our lower bound is for many Boolean sums the first nontrivial lower bound. On the other side we can prove that the best lower bound which the main theorem yields is the n ^3/2-bound cited above. For the proof we use the technical trick of assuming that certain functions are given for free.     

The depth of monotone Boolean functions with multi input “AND” and “OR” gates

The problem of maximum depth of monotone Boolean functions is investigated when k-input AND and OR gates are used for realisation.     

Linear multi-secret sharing schemes

In this paper the linear multi-secret sharing schemes are studied by using monotone span programs. A relation between computing monotone Boolean functions by using monotone span programs and realizing multi-access structures by using linear multi-secret sharing schemes is shown. Furthermore, the concept of optimal linear multi-secret sharing scheme is presented and the several schemes are proved to be optimal.     

The Monotone Circuit Complexity of Quadratic Boolean Functions

Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which have only one level of AND gates, and arbitrary monotone circuits, and show that there is an exponential gap between the conjunctive complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Nearly tight upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over all quadratic functions are also proved. Moreover, we describe the way of lower bounding the single level circuit complexity and give a set of quadratic functions whose monotone complexity is strictly smaller than its single level complexity.     

On another Boolean matrix

In his paper “On a Boolean matrix”, Nechiporuk gave an explicit example of a set of n homogeneous monotone Boolean functions of the first degree in n variables that require Ω(n^3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n^5/3) two-input gates.     

A 4n-lower bound on the monotone network complexity of a one-output boolean function

The main purpose of Boolean network theory is to find functions f:{0, 1}ⁿ → {0, 1} with large network complexity. The best known lower bound over the complete basis of all binary functions is of size 3n for a non-monotone function (Blum (1982)). Bloniarz (1979) has proved a 3n-lower bound for the majority-function over the monotone basis. In this paper a special function is presented for which a lower bound of size 4n over the monotone basis can be proved.     

Picture-Hanging Puzzles

We show how to hang a picture by wrapping rope around n nails, making a polynomial number of twists, such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed. This construction makes for some fun mathematical magic performances. More generally, we characterize the possible Boolean functions characterizing when the picture falls in terms of which nails get removed as all monotone Boolean functions. This construction requires an exponential number of twists in the worst case, but exponential complexity is almost always necessary for general functions.     

Extracting rules from trained neural networks

Presents an algorithm for extracting rules from trained neural networks. The algorithm is a decompositional approach which can be applied to any neural network whose output function is monotone such as a sigmoid function. Therefore, the algorithm can be applied to multilayer neural networks, recurrent neural networks and so on. It does not depend on training algorithms, and its computational complexity is polynomial. The basic idea is that the units of neural networks are approximated by Boolean functions. But the computational complexity of the approximation is exponential, and so a polynomial algorithm is presented. The author has applied the algorithm to several problems to extract understandable and accurate rules. The paper shows the results for the votes data, mushroom data, and others. The algorithm is extended to the continuous domain, where extracted rules are continuous Boolean functions. Roughly speaking, the representation by continuous Boolean functions means the representation using conjunction, disjunction, direct proportion, and reverse proportion. This paper shows the results for iris data.     

Extension of belief functions to infinite-valued events

We generalise belief functions to many-valued events which are represented by elements of Lindenbaum algebra of infinite-valued ?ukasiewicz propositional logic. Our approach is based on mass assignments used in the Dempster–Shafer theory of evidence. A generalised belief function is totally monotone and it has Choquet integral representation with respect to a unique belief measure on Boolean events.     

Entropy of capacities on lattices and set systems

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.     

Which bases admit non-trivial shrinkage of formulae?

We show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis B of Boolean functions, is strictly greater than 1 if and only if all the functions in B are unate, i.e., monotone increasing or decreasing in each of their variables. As a consequence, we get non-linear lower bounds on the formula complexity of the parity function over any basis composed only of unate functions. Received: June 15, 2000.     

On the complexity of 2-output Boolean networks

The complexity of 2-output combinational networks without feedback is explored. For monotone networks, which contain only and-gates and or-gates, if the two outputs can be expressed as Boolean functions having at most one variable in common, then the network obtained by adjoining optimal realizations of the individual functions is optimal. This property fails if the number of common input variables is greater than one or when not-gates are allowed.