On another view of an inverse of an interval matrix

We consider n × n matrix whose elements are fuzzy numbers (hereinafter a fuzzy matrix) and we introduce notions of regularity of a fuzzy matrix and the inverse matrix of a fuzzy matrix (hereinafter the fuzzy inverse) in this paper. It is shown that the fuzzy inverse is a fuzzy matrix as well. Also we pay attention to the calculation of the fuzzy inverse in a special case. Main results are based on Rohn’s results in the field of linear problems with inexact data.     

Understanding one another: making out meanings with Boolean equations

Autonomous ai agents raise the issue of semantic interoperability between independently architectured and differently embodied intelligences. This article offers an approach to the issue with certain aspects that are close in spirit to the way humans make out meanings. Using a mathematical model of cognition, it is shown how agents with autonomously developed conceptualizations can bootstrap and unravel each other’s meanings ad hoc. The domain general methodology is based on the agents’ capability to deal with Boolean operations, and on the shared outside environment. No prior provisions are required. The formalized cognitive process consists of constructing, and solving, Boolean equations that are grounded in the shared environment. The process yields a testable conjecture about the grounded conceptual representation of the other, along with a testable conjectured translation that maps from that representation to one’s own.      

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.     

Constructing irreducible coverings of a Boolean matrix

A polynomial delay algorithm for searching for irreducible coverings of a Boolean matrix is constructed. A similar result is obtained for the problem of constructing maximal conjunctions of a monotone Boolean function specified by its conjunctive normal form. Elena V. Djukova born 1945. Graduated from Moscow State University in 1967. Candidate’s degree in Physics and Mathematics in 1979. Doctoral degree in Physics and Mathematics in 1997. Dorodnicyn Computing Center, Russian Academy of Sciences, leading researcher. Moscow State University, lecturer. Moscow Pedagogical University, lecturer. Scientific interests: discrete mathematics and mathematical methods of pattern recognition. Author of 76 papers. Andrey S. Inyakin born 1978. Graduated from Moscow State University in 2000. Candidate’s degree in Physics and Mathematics in 2000. Dorodnicyn Computing Center, Russian Academy of Sciences, junior researcher. Scientific interests: discrete mathematics and mathematical methods of pattern recognition. Author of sixteen papers.     

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     

On detecting faults for Boolean expressions

Fault based testing aims at detecting hypothesized faults based on specifications or program source. There are some fault based techniques for testing Boolean expressions which are commonly used to model conditions in specifications as well as logical decisions in program source. The MUMCUT strategy has been proposed to generate test cases from Boolean expressions. Moreover, it detects eight common types of hypothesized faults provided that the original expression is in irredundant disjunctive normal form, IDNF. Software practitioners are more likely to write the conditions and logical decisions in general form rather than IDNF. Hence, it is interesting to investigate the fault detecting capability of the MUMCUT strategy with respect to general form Boolean expressions. In this article, we perform empirical studies to investigate the fault detection capability of the MUMCUT strategy with respect to general form Boolean expressions as well as mutated expressions. A mutated expression can be obtained from the original given Boolean expression by making a syntactic change based on a particular type of fault.

On the equal-weight symmetric Boolean functions

Two important classes of symmetric Boolean functions are the equal-weight Boolean functions and the elementary (or homogeneous) symmetric Boolean functions. In this paper we studied the equal-weight symmetric Boolean functions. First the Walsh spectra of the equal-weight symmetric Boolean functions are given. Second the sufficient and necessary condition on correlation-immunity of the equal-weight symmetric Boolean function is derived and other cryptology properties such as the nonlinearity, balance and propagation criterion are taken into account. In particular, the nonlinearity of the equal-weight symmetric Boolean functions with n (n ≥ 10) variables is determined by their Hamming weight. Considering these properties will be helpful in further investigations of symmetric Boolean functions.     

有限布尔环上的自动机

自动机理论作为计算机科学的基础理论，其研究直接地推动计算机科学技术的发展．本文研究了有限布尔环上的自动机，首次定出了有限布尔环上的一类下向树和一类有向圈，并证明了布尔环上的一类可逆内动机的图型与其仿射内动机的图型相同．     

On cross-correlation properties of Boolean functions

The relationship among cross-correlation of arbitrary four Boolean functions is presented. Several known cross-correlation properties of Boolean functions are generalized. Based on them, a lower bound for the maximal cross-correlation (in absolute value) of two Boolean functions (if one of the functions is bent) is obtained.     

On computation of Boolean involutive bases

Gröbner bases in Boolean rings can be calculated by an involutive algorithm based on the Janet or Pommaret division. The Pommaret division allows calculations immediately in the Boolean ring, whereas the Janet division implies use of a polynomial ring over field \(\mathbb{F}_2 \). In this paper, both divisions are considered, and distributive and recursive representations of Boolean polynomials are compared from the point of view of calculation effectiveness. Results of computer experiments with both representations for an algorithm based on the Pommaret division and for lexicographical monomial order are presented.     

On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the columns is frequent if there are at least t rows having a 1 entry in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. We consider the complexity aspects of frequent sets. An explicit family of subsets is given that requires exponentially many rows to be represented as the family of frequent sets of a matrix, with any threshold. Examples are given of families that can be represented by a small matrix with threshold t, but that require a significantly larger matrix if the threshold is less than t. We also discuss the connections of these problems to circuit complexity and the existence of efficient listing algorithms. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the independence of Boolean functions

Boolean functions are widely used because they can be used to precisely describe logical circuits. Properties of Boolean functions with respect to their applications to cryptography have been studied, but relationship between Boolean functions are rarely studied. This paper studies the independence of Boolean functions, gives necessary and sufficient conditions for judging whether two given Boolean functions are independent. Some enumeration formulae are given.     

On Restricted-Focus-of-Attention Learnability of Boolean Functions

In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While thek -RFA model is a natural extension of the PAC model, there are also significant differences. For example, it was previously known that learnability in this model is not characterized by the VC-dimension and that many PAC learning algorithms are not applicable in the k-RFA setting.In this paper we further explore the relationship between the PAC and k -RFA models, with several interesting results. First, we develop an information-theoretic characterization of k-RFA learnability upon which we build a general tool for proving hardness results. We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes,k -decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs. Among other results, we prove a hardness result for k-RFA learnability of k-DL,k n-2 . In sharp contrast, an (n-1)-RFA algorithm for learning (n-1)-DL is presented. Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance. In addition, we show that there is a uniform-distribution k-RFA learning algorithm for the class of k -DL. For k-TOP we show weak learnability by ak -RFA algorithm (with efficient time and sample complexity for constant k) and strong uniform-distribution k-RFA learnability of k-TOP with efficient sample complexity for constant k. Finally, by combining some of our k-DL and k-TOP results, we show that, unlike the PAC model, weak learning does not imply strong learning in the k -RFA model.     

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.