Approximation of Boolean Functions by Local Search

Usually, local search methods are considered to be slow. In our paper, we present a simulated annealing-based local search algorithm for the approximation of Boolean functions with a proven time complexity that behaves relatively fast on randomly generated functions. The functions are represented by disjunctive normal forms (DNFs). Given a set of m uniformly distributed positive and negative examples of length n generated by a target function F(x ₁,...,x _n), where the DNF consists of conjunctions with at most literals only, the algorithm computes with high probability a hypothesis H of length m · such that the error is zero on all examples. Our algorithm can be implemented easily and we obtained a relatively high percentage of correct classifications on test examples that were not presented in the learning phase. For example, for randomly generated F with n = 64 variables and a training set of m = 16384 examples, the error on the same number of test examples was about 19% on positive and 29% on negative examples, respectively. The proven complexity bound provides the basis for further studies on the average case complexity.     

Covering Sequences of Boolean Functions and Their Cryptographic Significance

We introduce the notion of covering sequence of a Boolean function, related to the derivatives of the function. We give complete characterizations of balancedness, correlation immunity and resiliency of Boolean functions by means of their covering sequences. By considering particular covering sequences, we define subclasses of (correlation-immune) resilient functions. We derive upper bounds on their algebraic degrees and on their nonlinearities. We give constructions of resilient functions belonging to these classes. We show that they achieve the best known trade-off between order of resiliency, nonlinearity and algebraic degree.     

The Mean-value of Meromorphic Functions with Respect to a Generalized Boolean Transformation

A formula for the mean-value distribution of certain meromorphic functions on a vertical line s = σ +iR under a generalized Boolean transformation, called rational Boolean transformation from R into itself, is derived using Birkhoff 's ergodic theorem. This formula is represented as a computable integral. Using the Cauchy's integral theorem, values of this integral corresponding to various possible cases are explicitly computed.     

Variable orderings and the size of OBDDs for random partially symmetric Boolean functions

The size of ordered binary decision diagrams (OBDDs) strongly depends on the chosen variable ordering. It is an obvious heuristic to use symmetric variable orderings, i.e., variable orderings where symmetric variables are arranged adjacently. In order to evaluate this heuristic, methods for estimating the OBDD size for random partially symmetric functions are presented. Characterizations of cases where, with high probability, only symmetric variable orderings and, with high probability, only nonsymmetric variable orderings lead to minimum OBDD size are obtained. For this analysis estimates for the number of different blocks of random Boolean matrices are used. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 49–70, 1998     

The Berman Conjecture Is True for Finite Surjective Semigroups and Their Inflations

A semigroup S is called surjective if S ² =S . The aim of this paper is to prove that p _n -sequences of finite surjective semigroups are eventually strictly increasing, except in few well known cases, when they are bounded. Also, some further types of finite semigroups, obtained by means of subdirect products, are shown to have the same property.     

An Upper Bound on the Number of Iterations for Transforming a Boolean Function of Degree Greater or Equal Than 4 to a Function of Degree 3

The difficulty involved in characterizing the weight distribution of all Boolean functions of degree 3 is well-known [2, p. 446]. In [1] the author introduces a transformation on Boolean functions which changes their weights in a way that is easy to follow, and which, when iterated, reduces the degree of the function to 2 or 3. He concludes that it is just as difficult to characterize the weight of any function of degree 3 as it is for any other degree. The application of this transformation on a Boolean function defined on , increases the number of its variables by two. On the other hand, in order to reduce the degree of a function to 2 or 3 it is necessary to apply the tranformation a number of times that grows exponentially with respect to m. In this paper, a factorization method on Boolean functions that allows the establishment of an upper bound for the number of applications of the transformation is presented. It shows that, in general, it is possible to significantly decrease the number of iterations in this process of degree reduction.     

Interpolation Formula for Functions of Several Variables

Mathematical Notes -     

P ≠ NP for all infinite Boolean algebras

We prove that all infinite Boolean rings (algebras) have the property P ≠ NP according to the digital (binary) nondeterminism.     

The Merrifield–Simmons Conjecture Holds for Bipartite Graphs

Let be a graph and the number of independent (vertex) sets of G. Then the Merrifield–Simmons conjecture states that the sign of the term only depends on the parity of the distance of the vertices in G. We prove that the conjecture holds for bipartite graphs by considering a generalization of the term, where vertex subsets instead of vertices are deleted.     

The Bergman–Sce transform for slice monogenic functions

In a recent paper, we showed that the classical Bergman theory admits two possible formulations for the class of slice regular functions with quaternionic values. In the so called formulation of the first kind, we provide a Bergman kernel which is defined on and is a reproducing kernel. In the so called formulation of the second kind, we use the Representation Formula for slice regular functions to define a second Bergman kernel; this time the kernel is still defined on U, but the integral representation of f is based on an integral computed only on and the integral does not depend on , (here denotes the sphere unit of purely imaginary quaternions, and represents the complex plane with imaginary unit I). In this paper, we extend the second formulation of the Bergman theory to the case of slice monogenic functions and we focus our attention on the so‐called Bergman–Sce transform. This integral transform is defined by using the Bergman kernel and the Sce mapping theorem and associates to every slice monogenic function f, an axially monogenic function . Copyright © 2011 John Wiley & Sons, Ltd.     

Weierstrass-Mandelbrot函数的非单调类性

非单调类性质在连续函数研究中起着重要作用．众所周知，Weierstrass函数具有非单调类性质．本文证明了Weierstrass-Mandelbrot型函数具有非单调类性质．     

On Extension and Continuity of p–Additive Functions

In this paper we prove some properties of p–additive functions as well as p–additive set–valued functions.     

一种SPA记分函数的多属性决策方法

在集对分析(SPA)理论基础上,结合集对分析联系数同、异、反之间的关系及内在规律,提出了SPA集记分函数的概念,并讨论了其含义特性.据此建立了一种基于SPA记分函数的多属性信息决策方法.最后,通过实例说明该方法的具体计算过程及步骤.     

Robustness in complex information systems: The role of information “barriers” in Boolean networks

In this supposed “information age,” a high premium is put on the widespread availability of information. Access to as much information as possible is often cited as key to the making of effective decisions. While it would be foolish to deny the central role that information and its flow has in effective decision‐making processes, this chapter explores the equally important role of “barriers” to information flows in the robustness of complex systems. The analysis demonstrates that (for simple Boolean networks at least) a complex system's ability to filter out, i.e., block, certain information flows is essential if it is not to be beholden to every external signal. The reduction of information is as important as the availability of information. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

The Weak Convergence for Functions of Negatively Associated Random Variables

Let {X_n, n1} be a sequence of stationary negatively associated random variables, S_j(l)=∑^l_i=1 X_j+i, S_n=∑ⁿ_i=1 X_i. Suppose that f(x) is a real function. Under some suitable conditions, the central limit theorem and the weak convergence for sums are investigated. Applications to limiting distributions of estimators of Var S_n are also discussed.     

The Cascade Algorithm for the Numerical Computation of Refinable Functions

The cascade algorithm is a method which can be used for the computation of refinable functions. We prove here that in general the cascade algorithm will not inherit the accuracy and refinability of the limit refinable function. We provide conditions for which the cascade iteration does indeed preserve accuracy.     

The Dempster–Shafer calculus for statisticians

The Dempster–Shafer (DS) theory of probabilistic reasoning is presented in terms of a semantics whereby every meaningful formal assertion is associated with a triple (p, q, r) where p is the probability “for” the assertion, q is the probability “against” the assertion, and r is the probability of “don’t know”. Arguments are presented for the necessity of “don’t know”. Elements of the calculus are sketched, including the extension of a DS model from a margin to a full state space, and DS combination of independent DS uncertainty assessments on the full space. The methodology is applied to inference and prediction from Poisson counts, including an introduction to the use of join-tree model structure to simplify and shorten computation. The relation of DS theory to statistical significance testing is elaborated, introducing along the way the new concept of “dull” null hypothesis.     

The Plancherel--Rotach Formula for Chebyshev--Hermite Functions on Half-Intervals Contracting to Infinity

In this paper, we prove the Plancherel--Rotach asymptotic formula for the Chebyshev--Hermite functions and their derivatives for the case in which belongs to the domain of definition. A method for calculating the approximation accuracy is also given.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.