A New Approach to the Decomposition of Boolean Functions by the Method of q-Partitions. II. Repeated Decomposition

A new approach to the decomposition of Boolean functions that depend on n variables and are represented in various forms is considered. The approach is based on the method of #-partitioning of minterms and on the introduced concept of a decomposition clone. The theorem on simple disjunctive decomposition of full and partial functions is formulated. The approach proposed is illustrated by examples.     

Decomposition of Separable Concave Structuring Functions

This paper presents a decomposition scheme for a large class of greyscale concave structuring functions from mathematical morphology. In contrast with many existing decomposition schemes, our method is valid in the continuous domain. Conditions are given under which this continuous method can be properly discretized. The class of functions that can be decomposed with our method contains all concave 2D-functions that are separable in two 1D-functions. This class contains the class of quadratic functions, that are of major importance in, for instance, distance transforms and morphological scale space. In the continuous domain, the size of the structuring elements resulting from the decomposition, can be chosen arbitrarily small. Conditions under which the discrete version of the decomposition can be guaranteed are given. For functions from the mentioned class, that can be separated along the standard image axes, a discrete decomposition in elements of n × n pixels is always possible, with n 3. The parabola fall in the atter category.     

A new approach to the decomposition of Boolean functions by the method of <Emphasis Type="Italic">q</Emphasis>-partitions. III. Joint decomposition of a function system

The paper considers the set-theoretical approach to the joint decomposition of systems of Boolean functions of variables specified in different representation forms. The approach is based on the method of q-partitions of conjuncterms and concept of decomposition clones. Theorems on joint decomposition of a system of full and partial functions are formulated. The approach is illustrated by examples. Parts I and II of this article are published in No. 5 (2001) and No. 1 (2002). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 39–58, March–April 2007.     

A New Method of Coding Minorants in Problems of Synthesis of Digital Devices from PLAs

A new method of coding minorants in decomposing a system of Boolean function is proposed. The method is based on the initial coding obtained from the minimal representation of the system in the so-called set-theoretical decomposition form obtained as a result of q-partitioning of conjuncterms of functions represented in DNF. A distinctive feature of the method is the preservation of the correspondence of the obtained codes of minorants to the block structure of the system being decomposed, which provides the minimum of informational capacity of PLAs.     

PARACONSISTENT LOGIC (in Italian), by Nicola Grana. Lofredo Editore,Naples, 1983. 134 pp.

Modified Reconstructibility Analysis (MRA), a novel decomposition within the framework of set-theoretic (crisp possibilistic) reconstructibility analysis, is presented. It is shown that in some cases, while three-variable NPN-classified Boolean functions are not decomposable using Conventional Reconstructibility Analysis (CRA), they are decomposable using MRA. Also, it is shown that whenever a decomposition of three-variable NPN-classified Boolean functions exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. A comparison of the corresponding complexities for Ashenhurst-Curtis decompositions and MRA is also presented. While both AC and MRA decompose some but not all NPN-classes, MRA decomposes more classes, and consequently more Boolean functions. MRA for many-valued functions is also presented, and algorithms using two different methods (intersection and union) are given. A many-valued case is presented where CRA fails to decompose but MRA decomposes.     

Structure-Texture Image Decomposition—Modeling, Algorithms, and Parameter Selection

This paper explores various aspects of the image decomposition problem using modern variational techniques. We aim at splitting an original image f into two components u and ρ, where u holds the geometrical information and ρ holds the textural information. The focus of this paper is to study different energy terms and functional spaces that suit various types of textures. Our modeling uses the total-variation energy for extracting the structural part and one of four of the following norms for the textural part: L², G, L¹ and a new tunable norm, suggested here for the first time, based on Gabor functions. Apart from the broad perspective and our suggestions when each model should be used, the paper contains three specific novelties: first we show that the correlation graph between u and ρ may serve as an efficient tool to select the splitting parameter, second we propose a new fast algorithm to solve the TV − L¹ minimization problem, and third we introduce the theory and design tools for the TV-Gabor model. First online version published in February, 2006     

On Complexity of Computation of Partial Derivatives of Boolean Functions Realized by Zhegalkin Polynomials

The combinational complexity of a system of partial derivatives in the basis of linear functions is established for a Boolean function of n variables that is realized by a Zhegalkin polynomial. An algorithm whose complexity equals 3ⁿ – 2ⁿ modulo 2 additions is proposed for computation of all partial derivatives of such a function from the coefficients of its Zhegalkin polynomial.     

A new approach to the decomposition of boolean functions. 4. non-disjoint decomposition: the method of <Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">q</Emphasis>-partitions

A set-theoretical approach to the non-disjoint decomposition of different forms of representation of Boolean functions of n variables is considered. This approach is based on the method of p,q-partitions of conjuncterms and on the concept of a decomposition clone. Two techniques of searching for some non-disjoint functional decomposition are described. Theorems on the non-disjoint decomposition of full and partial functions and their systems are formulated. The proposed approach is illustrated by examples. Parts I, II, and III of this article are published in No. 5 (2001), No. 1 (2002), and No. 2 (2007). Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 15-41, May–June 2009.     

Canonical Decomposition of Steerable Functions

This paper describes a general mathematical formulation for the problem of constructing steerable functions. The formulation is based on Lie group theory and is thus applicable to transformations which are Lie groups, such as, rotation, translation, scaling, and affine transformation. For one-parameter and Abelian multi-parameter Lie transformation groups, a canonical decomposition of all possible steerable functions, derived using the Jordan decomposition of matrices, is developed. It is shown that any steerable function under Lie transformation groups can be described using this decomposition. Finally, a catalog of steerable functions for several common multi-parameter image transformation groups is also provided.     

Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions

The two-party communication complexity of Boolean function f is known to be at least log rank (M _f ), i.e., the logarithm of the rank of the communication matrix of f [19]. Lovász and Saks [17] asked whether the communication complexity of f can be bounded from above by (log rank (M _f )) ^c , for some constant c . The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f , it remained a difficult open problem. We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L ₁ norm of function f , for arbitrary Boolean function f . Received August 24, 1996; revised October 15, 1997.     

A Class of Functions from P 2

A number of essential properties of a class G of Boolean functions are investigated; these functions are realized by functional elements that have one output and check tests of length two that detect single constant errors at inputs and outputs of these elements. The problem of completeness of this class and questions of its relation to closed base classes in P ₂ are considered. A lower estimate of the number of all the functions of n variables from this class is obtained.     

Bessel function of the first kind with complex argument

A new method of computing integral order Bessel functions of the first kind J_n(z) when either the absolute value of the real part or the imaginary part of the argument z = x + iy is small, is described. This method is based on computing the Bessel functions from asymptotic expressions when x∼ 0 (or y ∼ 0). These expansions are derived from the integral definition of Bessel functions. This method is necessary because some existing algorithms and methods fail to give correct results for small x small y. In addition, our overall method of computing Bessel functions of any order and argument is discussed and the logarithmic derivative is used in computing these functions. The starting point of the backward recurrence relations needed to evaluate the Bessel function and their logarithmic derivatives are investigated in order to obtain accurate numerical results. Our numerical method, together with established techniques of computing the Bessel functions, is easy to implement, efficient, and produces reliable results for all z.     

A General Decomposition Theorem for the k-Server Problem

The first general decomposition theorem for the k-server problem is presented. Whereas all previous theorems are for the case of a finite metric with k+1 points, the theorem given here allows an arbitrary number of points in the underlying metric space. This theorem implies O(polylog(k))-competitive randomized algorithms for certain metric spaces consisting of a polylogarithmic number of widely separated subspaces and takes a first step toward a general O(polylog(k))-competitive algorithm. The only other cases for which polylogarithmic competitive randomized algorithms are known are the uniform metric space and the weighted cache metric space with two weights.     

An extension theorem for polynomials on triangles

We present an extension theorem for polynomial functions that proves a quasi-optimal bound for a lifting from L ² on edges onto a fractional-order Sobolev space on triangles. The extension is such that it can be further extended continuously by zero within the trace space of H ¹. Such an extension result is critical for the analysis of non-overlapping domain decomposition techniques applied to the p-and hp-versions of the finite and boundary element methods for elliptic problems of second order in three dimensions. Supported by the FONDAP Programme in Applied Mathematics, Chile.     

Convex Hodge Decomposition and Regularization of Image Flows

The total variation (TV) measure is a key concept in the field of variational image analysis. In this paper, we focus on vector-valued data and derive from the Hodge decomposition of image flows a definition of TV regularization for vector-valued data that extends the standard componentwise definition in a natural way. We show that our approach leads to a convex decomposition of arbitrary vector fields, providing a richer decomposition into piecewise harmonic fields rather than piecewise constant ones, and motion texture. Furthermore, our regularizer provides a measure for motion boundaries of piecewise harmonic image flows in the same way, as the TV measure does for contours of scalar-valued piecewise constant images.

Information Preserving Time Decompositions of Time Stamped Documents*

Extraction of sequences of events from news and other documents based on the publication times of these documents has been shown to be extremely effective in tracking past events. This paper addresses the issue of constructing an optimal information preserving decomposition of the time period associated with a given document set, i.e., a decomposition with the smallest number of subintervals, subject to no loss of information. We introduce the notion of the compressed interval decomposition, where each subinterval consists of consecutive time points having identical information content. We define optimality, and show that any optimal information preserving decomposition of the time period is a refinement of the compressed interval decomposition. We define several special classes of measure functions (functions that measure the prevalence of keywords in the document set and assign them numeric values), based on their effect on the information computed as document sets are combined. We give algorithms, appropriate for different classes of measure functions, for computing an optimal information preserving decomposition of a given document set. We studied the effectiveness of these algorithms by computing several compressed interval and information preserving decompositions for a subset of the Reuters–21578 document set. The experiments support the obvious conclusion that the temporal information gleaned from a document set is strongly dependent on the measure function used and on other user-defined parameters.

Decomposition of Algebraic Functions

Functional decomposition—whether a functionf(x) can be written as a composition of functionsg(h(x)) in a non-trivial way—is an important primitive in symbolic computation systems. The problem of univariate polynomial decomposition was shown to have an efficient solution by Kozen and Landau (1989). Dickerson (1987) and Gathen (1990a) gave algorithms for certain multivariate cases. Zippel (1991) showed how to decompose rational functions. In this paper, we address the issue of decomposition of algebraic functions. We show that the problem is related to univariate resultants in algebraic function fields, and in fact can be reformulated as a problem ofresultant decomposition. We characterize all decompositions of a given algebraic function up to isomorphism, and give an exponential time algorithm for finding a non-trivial one if it exists. The algorithm involves genus calculations and constructing transcendental generators of fields of genus zero.     

基于generalized dominator的BDD布尔表达式优化分解

BDD是布尔函数的一种图形表示方式,可以直观地反映出布尔函数的逻辑结构,利用BDD可以实现对布尔函数的分解和优化。针对BDD的数据结构和一种以generalizeddominators为基础的布尔表达式的优化方法进行研究,并且着重对其中的一种方法:连接的BDD分解方法(ConjunctiveBDDDecomposition)进行了详细的分析。     

一种密码函数存在性证明的新方法

密码函数在密码学中具有重要的研究价值.从组合的角度,给出了一种密码函数不存在性证明的新方法,并且得到了一些新结果,部分结果优于已有结论,这些结果可以部分证明不存在次数大于2的齐次旋转对称bent函数这一公开猜想.同时,利用多项式的最大公因子算法刻画了2次齐次旋转对称bent函数.该方法也可以用于刻画其他形式的bent函...