一个在Horn子句中求解极大缩减的算法

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.     

A general framework for computing maximal contractions

This paper investigates the problem of computing all maximal contractions of a given formula set Γ with respect to a consistent set Δ of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to compute all maximal contractions fromminimal inconsistent subsets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Finally, we demonstrate the ability of this framework by applying it to the first-order language without variables and design an algorithmfor the computation of all maximal contractions.     

Maximal contractions in Boolean algebras

In the present paper,the concepts of deductive element and maximal contraction are introduced in Boolean algebras,and corresponding theories of consistency and maximal contractions are studied.An algorithm principle is proposed to compute all maximal contractions for a consistent set with respect to its refutation in Boolean algebras.It is pointed out that the quotient algebra of the first-order language with respect to its provable equivalence relation constitutes a Boolean algebra,and hence the computation of R-contractions for closed formulas in first-order languages can be converted into the one in Boolean algebras proposed in this paper.Furthermore,the concept of basic element is introduced in Boolean algebras,which contributes to the definitions of clause and Horn clause transplanted from logic to a special type of Boolean algebras generated by basic elements.It is also pointed out that the computation of R-contractions for clauses in the classical propositional logic can be converted into the one in Boolean algebras generated by basic elements proposed in this paper.     

A decomposition based algorithm for maximal contractions

This paper proposes a decomposition based algorithm for revision problems in classical propositional logic. A set of decomposing rules are presented to analyze the satisfiability of formulas. The satisfiability of a formula is equivalent to the satisfiability of a set of literal sets. A decomposing function is constructed to calculate all satisfiable literal sets of a given formula. When expressing the satisfiability of a formula, these literal sets are equivalent to all satisfied models of such formula. A revision algorithm based on this decomposing function is proposed, which can calculate maximal contractions of a given problem. In order to reduce the memory requirement, a filter function is introduced. The improved algorithm has a good performance in both time and space perspectives.     

可能性理论与不相容知识处理

Ｄ．Ｄｕｂｏｉｓ和Ｈ．Ｐｒａｄｅ提出的可能性逻辑是一种基于可能性理论的非经典逻辑，主要和于不确定证据推理。可能性逻辑不同于模糊逻辑，因为模糊逻辑处理非布尔公式，其命题中包模糊谓词，而可能性逻辑处理布尔公式，其中只包含经典命题的和谓词。本文尝试在可能性理论的框架下进行不相容知识库的维护和问题求解。这里的知识表示是基于可能性逻辑的。为此，我们提出了两种不同的方法：第一种方法在计算命题可信度时，要考虑所     

Operational and complete approaches to belief revision

Two operational approaches to belief revision are presented in this paper.The rules of R-calculus are modified in order to deduce all the maximal consistent subsets.Another set of given in order to deduce all the minimal inconsistent subsets.Then a procedure,which can generate all the maximal consistent subsets,is presented.They are complete approaches,since all the maximal consistent subsets can be deduced or generated.In this paper,only the case of propositional logic is considered.     

Solutions to hybrid inclusions via set and graphical convergence with stability theory applications

Motivated by questions in stability theory for hybrid dynamical systems, we establish some fundamental properties of the set of solutions to such systems. Using the notion of a hybrid time domain and general results on set and graphical convergence, we establish under weak regularity and local boundedness assumptions that the set of solutions is sequentially compact and “upper semicontinuous” with respect to initial conditions and system perturbations. The general facts are then used to establish several results for the behavior of hybrid systems that have asymptotically stable compact sets. These results parallel what is already known for differential inclusions and difference inclusions. For example, the basin of attraction for a compact attractor is (relatively) open, the attractivity is uniform from compact subsets of the basin of attraction, and asymptotic stability is robust with respect to small perturbations.     

Motif patterns in 2D

Motif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.     

Minimal time function with respect to a set of directions: basic properties and applications

In this paper we study a special minimal time function, given with respect to a set of directions. Several properties, concerning continuity, convexity, Lipschitz behaviour and subdifferential calculus are explored. An application to a vectorial location problem is provided.     

Maximal unifiable subsets and minimal nonunifiable subsets

We address the problem of collecting information about failures and successes while unifying a set of equations. This is relevant to the study of efficient backtracking, for which Cox used the concept of maximal unifiable subsets while Bruynooghe and Pereira used a notion which is closely related to that of minimal non-unifiable subsets. As we show, both these concepts play a fundamental role in the process of exploring the search space for breadth first resolution in logic programs. In a special case they lead to similar search strategies but in general have complementary and even incompatible aspects. We then show that an algorithm due to Yasuura is particularly well suited as a basis for a method to construct the maximal unifiable subsets and minimal non-unifiable subsetsin conjunction with the unification process. In addition to its simplicity this method provides an answer for two problems raised by Cox concerning the preservation of successful partial computations and unification without occur check.     

Clique detection for nondirected graphs: Two new algorithms

Making use of special tree search algorithms the present paper describes two new methods for determining all maximal complete subgraphs (cliques) of a finite nondirected graph. In both methods the blockwise generation of all cliques induces characteristic properties, which guarantee an efficient calculation of special clique subsets, especially the set of all cliques of maximal length. Moreover, by their structure both algorithms allow to calculate the complete clique set by parallel processing. The algorithms have been tested for many series of characteristic graphs and compared with the algorithm of Bron-Kerbosch (Algorithm 457 of CACM) the most efficient algorithm which is known to the authors.     

基于集合枚举树的关联规则生成算法

在经典算法中由频繁项集生成关联规则需要生成频繁项集的所有非空子集作为候选后件集。李雄飞对此做出改进,提出逐层搜索后件的宽度优先算法。求下集极大元的Boundary算法也可用于求所有关联规则后件。论文提出一个深度优先算法GRSET(GenerateRulesbyusingSet-EnumerationTree),该算法利用集合枚举树,按照深度优先的方法逐一找出所有关联规则后件并得到相应的关联规则。通过实验对这三种算法进行比较,结果显示GRSET算法效率较高。     

A Nonlinear Integral Defined on Partition and its Application to Decision Trees

Nonlinear integrals play an important role in information fusion. So far, all existing nonlinear integrals of a function with respect to a set function are defined on a subset of a space. In many of the problems with information fusion, such as decision tree generation in inductive learning, we often need to deal with the function defined on a partition of the space. Motivated by minimizing the classification information entropy of a partition while generating decision trees, this paper proposes a nonlinear integral of a function with respect to a nonnegative set function on a partition, and provides the conclusion that the sum of the weighted entropy of the union of several subsets is not less than the sum of the weighted entropy of a single subset. It is shown that selecting the entropy of a single attribute is better than selecting the entropy of the union of several attributes in generating rules by decision trees.     

A note on robustness tolerances for combinatorial optimization problems

We consider so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of nonempty subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of the feasible solution. We assume that the set of feasible solutions is fixed, but the weights of elements may be perturbed or are given with errors. All possible realizations of weights form the set of scenarios.A feasible solution, which for a given set of scenarios guarantees the minimum value of the worst-case relative regret among all the feasible solutions, is called a robust solution. The maximum percentage perturbation of a single weight, which does not destroy the robustness of a given solution, is called the robustness tolerance of this weight with respect to the solution considered.In this paper we give formulae for computing the robustness tolerances with respect to an optimal solution obtained for some initial weights and we show that this can be done in polynomial time whenever the optimization problem is polynomially solvable itself.     

对象依赖和关键字的性质的初步研究

本文讨论了对象依赖集合和关键字的一些性质，首先给出有关对象依赖（OD）和关键字等的基本概念，然后讨论对象依赖的一些性质，最后给出并证明获取一个OD集合的所有关键字的JINGSI算法。     

Crossover invariant subsets of the search space for evolutionary algorithms

This paper addresses the relationship between schemata and crossover operators. In Appendix A a general mathematical framework is developed which reveals an interesting correspondence between the families of reproduction transformations and the corresponding collections of invariant subsets of the search space. On the basis of this mathematical apparatus it is proved that the family of masked crossovers is, for all practical purposes, the largest family of transformations whose corresponding collection of invariant subsets is the family of Antonisse's schemata. In the process, a number of other interesting facts are shown. It is proved that the full dynastic span of a given subset of the search space under either one of the traditional families of crossover transformations (one-point crossovers or masked crossovers) is obtained after [log2n] iterations where n is the dimension of the search space. The generalized notion of invariance introduced in the current paper unifies Radcliffe's notions of "respect" and "gene transmission". Besides providing basic tools for the theoretical analysis carried out in the current paper, the general facts established in Appendix A provide a way to extend Radcliffe's notion of "genetic representation function" to compare various evolutionary computation techniques via their representation.     

The Computing Capacity of Three-Input Multiple-Valued One-Threshold Perceptrons

In this paper, an exact and general formula is derived for the number of linear partitions of a given point set V in three-dimensional space, depending on the configuration formed by the points of V. The set V can be a multi-set, that is it may contain points that coincide. Based on the formula, we obtain an efficient algorithm for counting the number of k-valued logic functions simulated by a three-input k-valued one-threshold perceptron.     

On JSM reasoning applicable to unions of factbase subsets: Part 1

In this paper, we consider the strengthening of the JSM method for automated support of scientific research (ASSR JSM method) by introducing a ternary relationship of causality such that positive facts can contain negative causes and negative facts can contain positive causes. In this connection, we consider unions of factbase subsets that correspond to combinations of pairs of similarity predicates that, in turn, represent binary and ternary relationships of causality, respectively, for formalization of JSM reasoning rules.     

信念修正的完全和可操作的方法

给出了命题逻辑上信念修正的两种可操作的完全方法.首先对R-演算的规则进行了修改,使得对任何一个极大协调的子集都通过这组规则得到.然后,给出了求得所有的极小不协调子集的一组规则.最后,给出一个过程,该过程能求得所有的极大协调子集.因为这两种方法都能求得所有的极大协调子集,所以把它们称为完全的.     

Modeling dynamic relationship types for subsets of entity type instances and across entity types

In a traditional ER model, once we specify a subclass or superclass relationship, any changes to that relationship are treated as schema evolution. Further, ER models are rigid in the sense that once a relationship type is specified across a set of entity types, an instance of relationship type occur when one instance of all participating entity types are specified. Therefore, it is difficult to introduce in a simplified manner all relationship types across subsets of given set of entity types. In this paper, we provide mechanisms to model in our extended ER model: (i) specification of dynamic relationship types across subsets of instances of entity types, (ii) a simplified specification of relationships across subsets of given set of entity types, and (iii) mapping our extended ER model to relational database schema. We also show through an e-contract example the utility of our extended ER model.