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.     

Tree decomposition and discrete optimization problems: A survey

The paper considers tree decomposition methods as applied to discrete optimization and presents relevant mathematical results. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 102–118, July–August 2007.     

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.     

A multistage parallel-hierarchic network as a model of a neuronlike computation scheme

A three-dimensional network and its application to the analysis of images are described. This multilevel architecture studies partial correlations between structural components of an image. An algorithm is proposed that formalizes a new approach to the decomposition of images. An image is transformed so that each pixel contains information on the spatial structure of its neighborhood. The most correlated information is first formed, which ensures the resistance of the algorithm to small structural changes. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 114–133, March–April, 2000.     

A New Approach to the Decomposition of Boolean Functions by the Method of q-Partitions. I. Separating Decomposition of Full and Partial Functions

A new approach to the decomposition of Boolean functions of n variables is considered; the functions being decomposed can be represented in various forms. The approach is based on the method of q-partitions of minterms and on the introduced concept of a decomposition clone. The theorem on simple separating decomposition of full and partial functions is formulated. The approach proposed is illustrated by examples.     

Joint decomposition of Boolean functions on the basis of a solution of logic equations

It is proposed that the apparatus of logic equations be used to achieve an exact solution of the problem of joint decomposition of a system of Boolean functions with respect to a two-block partitioning of the set of arguments.     

A generalization of the Jensen inequality

A new approach for estimating functions and functionals based on the concept of function superconvexity and a generalization of the Jensen inequality is proposed. A new concept is introduced and the associated analytical results are substantiated. Some nontrivial estimates of functions are derived. Translated from Kibemetika i Sistemnyi Analiz, No. 2, pp. 89–99, March–April, 2000.     

Certain questions in solving block nonlinear optimization problems with coupling variables

A decomposition scheme for block nonlinear convex programming problems with coupling variables is considered. The possibility is examined of using approximated solutions of subproblems for generating subgradients of the functions that appear in the master problem. A regularization of the original problem that simplifies the master problem is considered. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 47–55, March–April 2006.     

A three-step decomposition method for the evolutionary design of sequential logic circuits

Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition, output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW system, namely 3SD–ES, which combines the 3SD method with the (μ, λ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library. The results demonstrate that 3SD–ES has much better performance in terms of scalability. It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.     

Empirical mode decomposition on skeletonization pruning

This paper presents a novel skeleton pruning approach based on a 2D empirical mode like decomposition (EMD-like). The EMD algorithm can decompose any nonlinear and non-stationary data into a number of intrinsic mode functions (IMFs). When the object contour is decomposed by empirical mode like decomposition (EMD-like), the IMFs of the object provide a workspace with very good properties for obtaining the object's skeleton. The theoretical properties and the performed experiments demonstrate that the obtained skeletons match to hand-labeled skeletons provided by human subjects. Even in the presence of significant noise and shape variations, cuts and tears, the resulted skeletons have the same topology as the original skeletons. In particular, the proposed approach produces no spurious branches as many existing skeleton pruning methods and moreover, does not displace the skeleton points, which are all centers of maximal disks.     

Associativity in combination of belief functions; a derivation of minC combination

 The nature of a contradiction (conflict) between two belief functions is investigated. Alternative ways of distributing the contradiction among nonempty subsets of frame of discernment are studied. The paper employes a new approach to understanding contradictions and introduces an original notion of potential contradiction. A method of an associative combination of generalized belief functions – minC combination and its derivation – is presented as part of the new approach. A proportionalization of generalized results is suggested as well. RID="*" ID="*" Support by Grant No. 1030803 of the GA AV ČR is acknowledged. I am grateful to Philippe Smets for a fruitful discussion on the topic.     

The quasi-newtonian method of solution of convex variational inequalities with descent decomposition

The problem of numerical solution of convex variational inequalities with nonlinear constraints is considered. An equivalent optimization problem is constructed. To solve it, a Newtonian-type method with descent decomposition with respect to direct and dual variables of a variational inequality is developed. The nonlocal convergence of the algorithm and the superlinear rate of convergence in a neighborhood of the solution are proved. Translated from Kibemetika i Sistemnyi Analiz, No. 4, pp. 90–105, July–August, 1999.     

Checking the satisfiability of formulas represented in disjunctive normal form in the language <Emphasis Type="Italic">L</Emphasis>. II

This paper concentrates on issues of implementation of the method proposed for checking the consistency of formulae of the language L and described in the first part of this work. Upper-bound estimates of time complexity of the corresponding algorithms are obtained. Part I of this article is published in No. 4 (2005). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 11–19, November–December 2005.     

Tangential decomposition

In this paper, we present the tangential block decomposition for block-tridiagonal matrices which is in many aspects similar to the frequency filtering method by Wittum [8] and also to the tangential frequency filtering decomposition by Wagner [6]–[7]. In opposite to the methods of Wittum and Wagner, for the class of model problems our approach does not use any test vectors for its implementation. Similar to many iterative methods, it needs only bounds for extremal eigenvalues. Theoretical properties of our scheme are similar to those for the ADI-method. The practical convergence of the presented method is illustrated by numerical examples.     

Subspace identification of closed loop systems by the orthogonal decomposition method

In this paper, we consider a problem of identifying the deterministic part of a closed loop system by applying the stochastic realization technique of (Signal Process. 52 (2) (1996) 145) in the framework of the joint input-output approach. Using a preliminary orthogonal decomposition, the problem is reduced to that of identifying the plant and controller based on the deterministic component of the joint input-output process. We discuss the role of input signals in closed loop identification and the realization method based on a finite data, and then sketch a subspace method for identifying state space models of the plant and controller. Since the obtained models are of higher order, a model reduction procedure should be applied for deriving lower order models. Some numerical results are included to show the applicability of the present technique.     

A Continuous problem of optimal partition with a nondifferentiable functional

A continuous problem of decomposition of an optimal set into disjoint subsets is considered. This problem is characterized by a non-differentiable performance criterion, the availability of a boundary-value problem for a parabolic type equation, and dependence of the initial condition function on the partition of some flat set. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 115–125, July–August, 2000.     

基于连接识别的协同进化种群分割算法研究

针对已有协同进化算法种群分割方法的不足,借鉴连接识别思想,提出用分段间隔相关迭代连接识别进行种群分割的算法,并给出算法的思想、步骤及具体实施方案．将其应用于典型的复杂函数优化问题,简要分析算法在搜索效率、计算复杂性等方面的性能以及相关参数对算法性能的影响,说明算法的可行性．     

Design sensitivity and reliability-based structural optimization by univariate decomposition

This paper presents a new univariate decomposition method for design sensitivity analysis and reliability-based design optimization of mechanical systems subject to uncertain performance functions in constraints. The method involves a novel univariate approximation of a general multivariate function in the rotated Gaussian space for reliability analysis, analytical sensitivity of failure probability with respect to design variables, and standard gradient-based optimization algorithms. In both reliability and sensitivity analyses, the proposed effort has been reduced to performing multiple one-dimensional integrations. The evaluation of these one-dimensional integrations requires calculating only conditional responses at selected deterministic input determined by sample points and Gauss–Hermite integration points. Numerical results indicate that the proposed method provides accurate and computationally efficient estimates of the sensitivity of failure probability, which leads to accurate design optimization of uncertain mechanical systems.     

Structural models of algorithms in problems of applied programming. II. Structural-algorithmic approach to software simulation

Relations existing between algorithms that are variously represented and are performed on various execution units are formalized. The process of software development is considered in the context of development and transformation of models. Possible applications of the structural-algorithmic approach are analyzed in various aspects of applied programming. Problems of analyzing algorithms in the context of execution of programs on computers are formulated. Part I of this article is published in No. 3 (2009). Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 49–56, July–August 2009.     

Parallel adaptive mesh generation and decomposition

An important class of methodologies for the parallel processing of computational models defined on some discrete geometric data structures (i.e. meshes, grids) is the so calledgeometry decomposition or splitting approach. Compared to the sequential processing of such models, the geometry splitting parallel methodology requires an additional computational phase. It consists of the decomposition of the associated geometric data structure into a number of balancedsubdomains that satisfy a number of conditions that ensure the load balancing and minimum communication requirement of the underlying computations on a parallel hardware platform. It is well known that the implementation of the mesh decomposition phase requires the solution of a computationally intensive problem. For this reason several fast heuristics have been proposed. In this paper we explore a decomposition approach which is part of a parallel adaptive finite element mesh procedure. The proposed integrated approach consists of five steps. It starts with a coarse background mesh that isoptimally decomposed by applying well known heuristics. Then, the initial mesh is refined in each subdomain after linking the new boundaries introduced by its decomposition. Finally, the decomposition of the new refined mesh is improved so that it satisfies the objectives and conditions of the mesh decomposition problem. Extensive experimentation indicates the effectiveness and efficiency of the proposed parallel mesh and decomposition approach.