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%.     

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.     

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     

浏览器扩展行为监控系统的设计与实现*

浏览器扩展是一种允许为浏览器添加个性化功能的机制。然而,这一机制在极大地增强了浏览器表现能力的同时,也使浏览器暴露在更多的攻击之下。为有效缓和浏览器扩展机制给用户带来的安全威胁,设计并实现了针对浏览器扩展的行为监控系统,通过一组安全策略来控制扩展对关键接口的访问;最后对该系统的有效性及性能进行了分析和测试。实验结果表明,系统可有效降低用户在使用浏览器扩展时所带来的安全风险。     

An average case analysis of a resolution principle algorithm in mechanical theorem proving

The satisfiability problem is a well known NP-complete problem. In artificial intelligence, solving the satisfiability problem is called mechanical theorem proving. One of those mechanical theorem proving methods is the resolution principle which was invented by J.R. Robinson. In this paper, we shall show how an algorithm based upon the resolution principle can be analyzed. Letn andr ₀ denote the numbers of variables and input clauses respectively. LetP ₀ denote the probability that a variable appears positively, or negatively, in a clause. Our analysis shows that the expected total number of clauses processed by our algorithm isO(n+r ₀) ifP ₀ is a constant,r ₀ is polynomially related withn, andn is large.This research was supported partially by the National Science Council of the Republic of China under the Grant NSC 78-0408-E007-06.     

Finite-time weighted average consensus with respect to a monotonic function and its application

The consensus state is an important and fundamental quantity for consensus problems of multi-agent systems, which indicates where all the dynamical agents reach. In this paper, weighted average consensus with respect to a monotonic function, which means that the trajectories of the monotonic function along the state of each agent reach the weighted average of their initial values, is studied for a group of kinematic agents with time-varying topology. By constructing a continuous nonlinear distributed protocol, such a consensus problem can be solved in finite time even though the time-varying topology involves unconnected graphs. Then the distributed protocol is employed to compute the maximum-likelihood estimation of unknown parameters over sensor networks. Compared with the existing results, the estimate scheme proposed here may reduce the costs of data communication, storage memory, book-keeping and computational overheads.     

可达性等价于状态方程可满足性的一个petri网子类

本文定义了一个petri网子类： ,满足条件 。本文证明：当目标标识 时,此petri网子类的可达性等价于状态方程 的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论：①对于满足 的每个非平凡的非负整数向量 ,都 ;②对于满足 的每个非平凡的非负整数向量 , 都是 的一个可执行向量。