Testing satisfiability of CNF formulas by computing a stable set of points

We show that a conjunctive normal form (CNF) formula F is unsatisfiable if and only if there is a set of points of the Boolean space that is stable with respect to F. So testing the satisfiability of a CNF formula reduces to looking for a stable set of points (SSP). We give some properties of SSPs and describe a simple algorithm for constructing an SSP for a CNF formula. Building an SSP can be viewed as a natural way of search space traversal. This naturalness of search space examination allows one to make use of the regularity of CNF formulas to be checked for satisfiability. We illustrate this point by showing that if a CNF F formula is symmetric with respect to a group of permutations, it is very easy to make use of this symmetry when constructing an SSP. As an example, we show that the unsatisfiability of pigeon-hole CNF formulas can be proven by examining only a set of points whose size is quadratic in the number of holes. Finally, we introduce the notion of an SSP with excluded directions and sketch a procedure of satisfiability testing based on the construction of such SSPs.     

Testing satisfiability of CNF formulas by computing a stable set of points

We show that a conjunctive normal form (CNF) formula F is unsatisfiable if and only if there is a set of points of the Boolean space that is stable with respect to F. So testing the satisfiability of a CNF formula reduces to looking for a stable set of points (SSP). We give some properties of SSPs and describe a simple algorithm for constructing an SSP for a CNF formula. Building an SSP can be viewed as a natural way of search space traversal. This naturalness of search space examination allows one to make use of the regularity of CNF formulas to be checked for satisfiability. We illustrate this point by showing that if a CNF F formula is symmetric with respect to a group of permutations, it is very easy to make use of this symmetry when constructing an SSP. As an example, we show that the unsatisfiability of pigeon-hole CNF formulas can be proven by examining only a set of points whose size is quadratic in the number of holes. Finally, we introduce the notion of an SSP with excluded directions and sketch a procedure of satisfiability testing based on the construction of such SSPs.     

A Necessary Condition about the Optimum Partition on a Finite Set of Samples and Its Application to Clustering Analysis

This paper presents another necessary condition about the optimum partition on a finite set of samples.From this condition,a corresponding generalized sequential hard k-means (GSHKM) clustering algorithm is built and many well-known clustering algorithms are found to be included in it.Under some assumptions the well-known MacQueen;s SHKM (Sequential Hard K-Means) algorithm,FSCL(Frequency Sensitive Competitive Learning) algorithm and RPCL (Rival Penalized Competitive Learning) algorithm are derived.It is shown that FSCL in fact still belongs to the kind of GSHKM clustering algorithm and is more suitable for producing means of K-partition of sample data,which is illustrated by numerical experiment.Meanwhile,some improvements on these algorithms are also given.     

The tree nearest on average to a given set of trees

We formulate the problem of constructing a tree which is the nearest on average to a given set of trees. The notion of “nearest” is formulated based on a conception of events such that counting their number makes it possible to distinguish each of the given trees from the desired one. These events are called divergence, duplication, loss, and transfer; other lists of events can also be considered. We propose an algorithm that solves this problem in cubic time with respect to the input data size. We prove correctness of the algorithm and a cubic estimate for its complexity.     

Solving a continuous nonlinear problem of optimal set partition with arrangement of subset centers in the case of a convex objective functional

A continuous nonlinear single-commodity problem of optimal partition of a set Ω in an n-measurable Euclidean space into disjoint subsets with arrangement of their centers is analyzed using equality and inequality constraints in the case of a convex objective functional. A method and algorithm are proposed to solve this problem. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 134–152, March–April 2008.     

Exact determinations of the maximal output admissible set for a class of nonlinear systems

This paper is concerned with obtaining necessary and sufficient conditions for fulfilling specified state and control pointwise-in-time constraints against a certain class of nonlinear dynamics. The results are generalizations of the maximal output admissible set theory to the case of nonlinear systems. Main contribution of the present paper is to propose explicit algorithmic procedures to determine the maximal output admissible set. Another contribution is that we discuss on a finite determinability of the maximal output admissible set for nonlinear systems. Some relations between observability of nonlinear systems and finite characterizations of the maximal output admissible set are clarified.     

Optimal lower bound for the extension of possibility measure to the power set of a set of elementary events

The concept of lower possibility measure is introduced and used to derive an existence criterion for the common extension of possibility measures to the power set of a set of elementary events. It is also used to derive an existence criterion for a model of convergence in probability for a sequence of distributions of fuzzy perceptive elements.     

Multivariable adaptive control as a natural extension of SISO adaptive control

The concepts of a potentially structural non-singularity and a structural non-singularity are introduced in this paper. Using these concepts, we derive the result that for almost all cases the plant to be controlled has a diagonal interactor by using an appropriate diagonal proper precompensator. Furthermore, both the precom-pensator and the interactor can be determined only from the structural information of T(s), the relative degrees of each element of T(s), without requiring any parametric information about T(s). Therefore, by assuming that the a priori knowledge of the plant consists of the relative degrees of each element of T(s) as well as the observability index of T(s), we can make MI MO adaptive control be quite a natural extension of SISO adaptive control.     

A mean string algorithm to compute the average among a set of 2D shapes

An algorithm to compute the mean shape, when the shape is represented by a string, is presented as a modification of the well-known string edit algorithm. Given N strings of symbols, a string edit sequence defines a mapping between their corresponding symbols. We transform these sets of mapped symbols (edges) into piecewise linear functions and we compute their mean. To transform them into functions, we use the equation of the line defining their edges, and the percentage of their length, in order to have a common parameterization. The algorithm has been experimentally tested in the computation of a representative among a class of shapes in a clustering procedure in the domain of a graphics recognition application.     

融合分区与Canny泛函的水平集对猴脑提取的研究

The traditional level set has randomness in the location selection of the initial contour, and lacks the processing of edge information. Therefore, accurate extraction of brain tissue edges cannot be achieved. Therefore, firstly, the level set algorithm of fusion partition and Canny functional fuses the idea of partition and combines the morphological information of each region to complete the initial contour position selection, so that the initial contour contains more brain tissue, and improve the efficiency of brain tissue extraction. Secondly, the Canny operator is integrated into the energy functional, which improves the accuracy of detecting the edge of the macaque brain tissue while retaining the superiority of the traditional level set on the uneven grayscale image. Results show that the algorithm achieves accurate extraction of macaque brain tissue with an accuracy of up to 86%.     

Exact and heuristic algorithms for balancing transfer lines when a set of available spindle heads is given

A balancing problem for paced tandem transfer lines with several spindle heads at each station is considered. A spindle head executes a block of operations. The set of all available spindle heads as well as the operations executed by each spindle head, the spindle head times and costs are known. There are operations with several spindle head candidates. The problem at the line design stage consists in the choice of spindle heads from the given set and their assignment to workstations. The goal is to minimize the line cost while satisfying the precedence, inclusion and exclusion constraints. An exact algorithm based on a mixed integer programming approach is developed. Two types of new heuristic algorithms are also suggested. One of them step‐by‐step assigns randomly spindle heads to a current workstation. The second uses depth‐first search techniques. Experimental results are reported.     

The generalized hybrid weighted average operator based on interval neutrosophic hesitant set and its application to multiple attribute decision making

The Neutrosophic set and Hesitant set are the important and effective tools to describe the uncertain information. In this paper, we combine the interval neutrosophic sets and interval-valued hesitant fuzzy sets, and propose the concept of the interval neutrosophic hesitant fuzzy set (INHFS) in order to use the advantages of them. Then, we present the operations and comparison method of INHFS, and develop some new aggregation operators for the interval neutrosophic hesitant fuzzy information, including interval neutrosophic hesitant fuzzy generalized weighted operator, interval neutrosophic hesitant fuzzy generalized ordered weighted operator, and interval neutrosophic hesitant fuzzy generalized hybrid weighted operator, and discuss some properties. Furthermore, we propose the decision-making method for multiple attribute group decision making with interval neutrosophic hesitant fuzzy information, and give the detail decision steps. Finally, we give an illustrate example to show the process of decision making.     

Approximation property of partition of unity and its applications

The linear combination of certain partition of unity, subordinate to certain open covering of a compact set, is proved to be capable of approximating to a continuous function at arbitrarily precision. By using proper open covering and partition of unity, the robust nonlinear controllers and adaptive laws are designed for a class of nonlinear systems with uncertainties. The states and parameters of the closed-loop systems can be stabilized in the meaning of UUB (uniformly ultimately bounded) via the robus tnonlinear controllers and adaptive laws. Finally, an example shows the validity of method in this paper.     

线性扩张状态观测器及其高阶形式的性能分析

扩张状态观测器(ESO)作为自抗扰控制(ADRC)的核心组件,其自身及高阶扩展形式的性能分析与评估至关重要.借助Lyapunov逆定理证明了任意扩张阶数下线性扩张状态观测器(LESO)重构状态误差的收敛性,并得出了观测误差上界与扩张阶数的定量关系式;在分别考虑扩张阶数、观测器带宽以及剪切频率的情况下,探讨了高阶及传统LESO的动态响应、干扰抑制能力与观测器参数间的关系;最后,结合改进的ADRC控制器,在估计能力、峰值现象的抑制、滤噪性能等方面对高阶及传统LESO进行了性能评估与仿真验证.所得出的结论可为ADRC应用中ESO的选取提供有效的理论依据.     

Reduced-order dynamic observer error linearisation: a natural extension of observer error linearisation

This paper introduces the concept of reduced-order dynamic observer error linearisation (RDOEL) for multi-output systems, which is the problem of transforming a nonlinear system into a nonlinear observer canonical form with the aid of auxiliary dynamics. The proposed RDOEL framework is not only a modified version of dynamic observer error linearisation (DOEL) but also a natural extension of observer error linearisation (OEL). We provide three necessary conditions for the RDOEL problem, and then derive a necessary and sufficient condition described in terms of Lie algebras of vector fields. Furthermore, from the result, we also give a geometric necessary and sufficient condition for the OEL problem, which has not yet been completely established in the case where a diffeomorphism on the output of general form is considered.     

A random set description of a possibility measure and its naturalextension

The relationship is studied between possibility and necessity measures defined on arbitrary spaces, the theory of imprecise probabilities, and elementary random set theory. It is shown how special random sets can be used to generate normal possibility and necessity measures, as well as their natural extensions. This leads to interesting alternative formulas for the calculation of these natural extensions