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.     

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.     

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.     

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.     

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.     

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.     

The technology of dynamic extension of attribute set for the search of satellite images in a database

The structures of metafiles for describing satellite images of the Earth we analyze in this article. We describe the architecture of interaction among the satellite images database components at the automated registration of new-type sensors. We offer the technology of dynamic extension of the attribute set for the search of satellite images in a database.     

Reducts of propositional theories,satisfiability relations,and generalizations of semantics of logic programs

Over the years, the stable-model semantics has gained a position of the correct (two-valued) interpretation of default negation in programs. However, for programs with aggregates (constraints), the stable-model semantics, in its broadly accepted generalization stemming from the work by Pearce, Ferraris and Lifschitz, has a competitor: the semantics proposed by Faber, Leone and Pfeifer, which seems to be essentially different. Our goal is to explain the relationship between the two semantics. Pearce, Ferraris and Lifschitz's extension of the stable-model semantics is best viewed in the setting of arbitrary propositional theories. We propose here an extension of the Faber–Leone–Pfeifer semantics, or FLP semantics, for short, to the full propositional language, which reveals both common threads and differences between the FLP and stable-model semantics. We use our characterizations of FLP-stable models to derive corresponding results on strong equivalence and on normal forms of theories under the FLP semantics. We apply a similar approach to define supported models for arbitrary propositional theories, and to study their properties.     

球面模型的逼近与数据压缩及推广

提出了一种三维物体表面的逼近表示与数据压缩方法.该方法可以在不增加表示物体表面的数据量(例如面片数量)的情况下,使逼近误差降低约1/2;在逼近误差不变的情况下,使表示物体表面的数据量大幅下降.提出了用与最基本的三维物体--球体表面相交的面片来表示球面的方法,将该方法扩展到了一般曲面.理论分析与实验数据表明,新算法与传统方法相比,其数据压缩比约为35%.该研究在虚拟现实技术和三维模型的数据压缩及传输等领域有较重要的学术及应用价值.     

Sine entropy of uncertain set and its applications

Entropy is used as a quantitative measurement of the information deficiency. In uncertain set theory, logarithm entropy for uncertain set has been proposed. However, it fails to measure the degree of uncertainty associated with some uncertain sets. Thus this paper will propose sine entropy for uncertain set as a supplement, and investigate its properties such as translation invariance and positive linearity. Besides, it proposes sine relative entropy for uncertain set, and gives its applications in portfolio selection and clustering.