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.     

An improved algorithm for Boolean matrix multiplication

A new algorithm for computing the product of two arbitraryN×N Boolean matrices is presented. The algorithm requiresO (N ³/logN) bit operations and onlyO(N logN) bits of additional storage. This represents an improvement on the Four Russians' method which requires the same number of operations but usesO(N ³/logN) bits of additional storage.     

The Boolean column and column-row matrix decompositions

Matrix decompositions are used for many data mining purposes. One of these purposes is to find a concise but interpretable representation of a given data matrix. Different decomposition formulations have been proposed for this task, many of which assume a certain property of the input data (e.g., nonnegativity) and aim at preserving that property in the decomposition. In this paper we propose new decomposition formulations for binary matrices, namely the Boolean CX and CUR decompositions. They are natural combinations of two previously presented decomposition formulations. We consider also two subproblems of these decompositions and present a rigorous theoretical study of the subproblems. We give algorithms for the decompositions and for the subproblems, and study their performance via extensive experimental evaluation. We show that even simple algorithms can give accurate and intuitive decompositions of real data, thus demonstrating the power and usefulness of the proposed decompositions.     

决策表中粗糙集的布尔矩阵表示

建立了布尔矩阵与逻辑方程组的解和决策表中的属性集之间的关系;然后在此基础上给出了决策表中的粗糙集理论的布尔矩阵表示;最后证明了属性约简在布尔矩阵和代数两种不同表示下是等价的。这些结论有助于人们深刻理解粗糙集理论的本质,同时为寻找高效的属性约简算法奠定了基础。     

Improved time and space bounds for Boolean matrix multiplication

Summary Using modular arithmetic we obtain the following improved bounds on the time and space complexities for n × n Boolean matrix multiplication: O(n ^log ₂ ⁷ lognlogloglognloglogloglogn) bit operations and O(n ²loglog n) bits of storage on a logarithmic cost RAM having no multiply or divide instruction; O(n ^log ₂ ⁷(logn)^2–1/2log ₂ ⁷(loglog n)^1/2log ₂ ^7–1) bit operations and O(n ²log n) bits of storage on a RAM which can use indirect addressing for table lookups. The first algorithm can be realized as a Boolean circuit with O(n ^log ₂ ⁷lognlogloglognloglogloglogn) gates. Whenever n×n arithmetic matrix multiplication can be performed in less than O(n ^log ₂ ⁷) arithmetic operations, our results have corresponding improvements.This work was supported in part by the Office of Naval Research under contract N00014-67-0204-0063, by the National Research Council of Canada under grant A4307, and by the National Science Foundation under grants MCS76-17321 and GJ-43332     

基于布尔推理的极大相容块构造方法

极大相容块是非完备信息系统中的最小知识单元,在非完备信息系统的知识表示、属性约简、粒度分析及知识获取方面有重要的应用价值。提出了一种获取非完备信息系统中极大相容块的方法。通过定义的区分关系,构造了新的布尔函数,证明了极大相容块与构造的布尔公式的素蕴含之间存在一一对应的关系。因此,这种新的布尔函数可以被用来获得系统的所有极大相容块,这将有助于非完备信息系统中的知识获取。     

Classification of Boolean functions by the invariants of their matrix representation

A variant of matrix representation for Boolean functions is designed such that these functions can be classified by matrix invariants. By way of example, the Deutsch problem is solved to illustrate the advantages of this classification.     

Boolean Algebra as a Fragment of the Theory of Boolean Toposes

Basic identities of Boolean algebra are considered, and their categorical analogs are proved.     

Derandomization,witnesses for Boolean matrix multiplication and construction of perfect hash functions

Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to design efficient algorithms for the All Pairs Shortest Path problem using fast matrix multiplication, solves the problem of computingwitnesses for the Boolean product of two matrices. That is, ifA andB are twon byn matrices, andC=AB is their Boolean product, the algorithm finds for every entryC _ij =1 a witness: an indexk so thatA _ik =B _kj =1. Its running time exceeds that of computing the product of twon byn matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfect hash function for a givenn-subset of {1,...,m}.Part of this paper was presented at the IEEE 33rd Symposium on Foundations of Computer Science.Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences. Some of this work was done while the author was with the IBM Almaden Research Center.     

基于改进的布尔矩阵约简算法的入侵检测方法

针对入侵检测数据特征维数多,通过改进的布尔矩阵约简算法对入侵数据样本进行属性约简,再应用灰色关联算法,使得原数据集中每条记录由原来的41个属性约简为27个,从而提高了入侵检测的速度和效率。实验结果也表明,应用此种约简方法,提高了入侵检测的效率,且保持了较为理想的检测率。     

Geometry of Translations on a Boolean Cube

Problems of Information Transmission - The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the...     

Boolean sets and most general solutions of Boolean equations

The aim of this paper is twofold. First we determine the most general form of the subsumptive general solution of a Boolean equation (Theorem 1 and Theorem 2). Then we discuss several characterizations of Boolean sets, meaning sets of zeros of Boolean functions, and prove that every Boolean transformation X=Φ(T) is the parametric general solution of a certain Boolean equation.     

Simulating Boolean Circuits on a DNA Computer

We demonstrate that DNA computers can simulate Boolean circuits with a small overhead. Boolean circuits embody the notion of massively parallel signal processing and are frequently encountered in many parallel algorithms. Many important problems such as sorting, integer arithmetic, and matrix multiplication are known to be computable by small size Boolean circuits much faster than by ordinary sequential digital computers. This paper shows that DNA chemistry allows one to simulate large semi-unbounded fan-in Boolean circuits with a logarithmic slowdown in computation time. Also, for the class NC ¹ , the slowdown can be reduced to a constant. In this algorithm we have encoded the inputs, the Boolean AND gates, and the OR gates to DNA oligonucleotide sequences. We operate on the gates and the inputs by standard molecular techniques of sequence-specific annealing, ligation, separation by size, amplification, sequence-specific cleavage, and detection by size. Additional steps of amplification are not necessary for NC ¹ circuits. The feasibility of the DNA algorithm has been successfully tested on a small circuit by actual biochemical experiments. Received May 29, 1997; revised February 15, 1998.