A Decision Procedure for Linear “Big O” Equations

Let F be the set of functions from an infinite set, S, to an ordered ring, R. For f, g, and h in F, the assertion f = g + O(h) means that for some constant C, |f(x) − g(x)| ≤C |h(x)| for every x in S. Let L be the first-order language with variables ranging over such functions, symbols for 0, +, −, min , max , and absolute value, and a ternary relation f = g + O(h). We show that the set of quantifier-free formulas in this language that are valid in the intended class of interpretations is decidable and does not depend on the underlying set, S, or the ordered ring, R. If R is a subfield of the real numbers, we can add a constant 1 function, as well as multiplication by constants from any computable subfield. We obtain further decidability results for certain situations in which one adds symbols denoting the elements of a fixed sequence of functions of strictly increasing rates of growth.     

An Optimal Decision Procedure for Right Propositional Neighborhood Logic

Propositional interval temporal logics are quite expressive temporal logics that allow one to naturally express statements that refer to time intervals. Unfortunately, most such logics turn out to be (highly) undecidable. In order to get decidability, severe syntactic or semantic restrictions have been imposed to interval-based temporal logics to reduce them to point-based ones. The problem of identifying expressive enough, yet decidable, new interval logics or fragments of existing ones that are genuinely interval-based is still largely unexplored. In this paper, we focus our attention on interval logics of temporal neighborhood. We address the decision problem for the future fragment of Neighborhood Logic (Right Propositional Neighborhood Logic, RPNL for short), and we positively solve it by showing that the satisfiability problem for RPNL over natural numbers is NEXPTIME-complete. Then, we develop a sound and complete tableau-based decision procedure, and we prove its optimality.     

An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints

Satisfiability Modulo Theories (SMT) have been widely investigated over the last decade. Recently researchers have extended SMT to the optimization problem over linear arithmetic constraints. To the best of our knowledge, Symba and OPT-MathSAT are two most efficient solvers available for this problem. The key algorithms used by Symba and OPT-MathSAT consist of the loop of two procedures: 1) critical finding for detecting a critical point, which is very likely to be globally optimal, and 2) global checking for confirming the critical point is really globally optimal. In this paper, we propose a new approach based on the Simplex method widely used in operation research. Our fundamental idea is to find several critical points by constructing and solving a series of linear problems with the Simplex method. Our approach replaces the algorithms of critical finding in Symba and OPT-MathSAT, and reduces the runtime of critical finding and decreases the number of executions of global checking. The correctness of our approach is proved. The experiment evaluates our implementation against Symba and OPT-MathSAT on a critical class of problems in real-time systems. Our approach outperforms Symba on 99.6% of benchmarks and is superior to OPT-MathSAT in large-scale cases where the number of tasks is more than 24. The experimental results demonstrate that our approach has great potential and competitiveness for the optimization problem.     

Decision procedures for extensions of the theory of arrays

The theory of arrays, introduced by McCarthy in his seminal paper “Towards a mathematical science of computation,” is central to Computer Science. Unfortunately, the theory alone is not sufficient for many important verification applications such as program analysis. Motivated by this observation, we study extensions of the theory of arrays whose satisfiability problem (i.e., checking the satisfiability of conjunctions of ground literals) is decidable. In particular, we consider extensions where the indexes of arrays have the algebraic structure of Presburger arithmetic and the theory of arrays is augmented with axioms characterizing additional symbols such as dimension, sortedness, or the domain of definition of arrays. We provide methods for integrating available decision procedures for the theory of arrays and Presburger arithmetic with automatic instantiation strategies which allow us to reduce the satisfiability problem for the extension of the theory of arrays to that of the theories decided by the available procedures. Our approach aims to re-use as much as possible existing techniques so as to ease the implementation of the proposed methods. To this end, we show how to use model-theoretic, rewriting-based theorem proving (i.e., superposition), and techniques developed in the Satisfiability Modulo Theories communities to implement the decision procedures for the various extensions.      

An Abstract Decision Procedure for Satisfiability in the Theory of Recursive Data Types

The theory of recursive data types is a valuable modeling tool for software verification. In the past, decision procedures have been proposed for both the full theory and its universal fragment. However, previous work has been limited in various ways. In this paper, we present a general algorithm for the universal fragment. The algorithm is presented declaratively as a set of abstract rules which are terminating, sound, and complete. We show how other algorithms can be realized as strategies within our general framework. Finally, we propose a new strategy and give experimental results showing that it performs well in practice.     

Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation

In this paper, we discuss the use of binary decision diagrams to represent general matrices. We demonstrate that binary decision diagrams are an efficient representation for every special-case matrix in common use, notably sparse matrices. In particular, we demonstrate that for any matrix, the BDD representation can be no larger than the corresponding sparse-matrix representation. Further, the BDD representation is often smaller than any other conventional special-case representation: for the n×n Walsh matrix, for example, the BDD representation is of size O(log n). No other special-case representation in common use represents this matrix in space less than O(n²). We describe termwise, row, column, block, and diagonal selection over these matrices, standard an Strassen matrix multiplication, and LU factorization. We demonstrate that the complexity of each of these operations over the BDD representation is no greater than that over any standard representation. Further, we demonstrate that complete pivoting is no more difficult over these matrices than partial pivoting. Finally, we consider an example, the Walsh Spectrum of a Boolean function.     

一种决策模型的自动生成及管理系统

本文说明了一种决策模型的自动生成及管理系统的设计与实现方法。该系统能够辅助人们去建立一种基于决策表的决策模型，自动进行各种检验，并能将此模型转换成另外两种决策模型。此外，它还具有决策模型库和应用案例库的管理功能。该系统已成功地运用到多个大型信息系统的开发之中。     

航空装备故障检测决策建模仿真研究

航空装备在飞机中数量较多,不同设备下的故障检测过程中,进行航空装备故障决策时,决策过程需要依赖较多的动态多源故障信息数据,但在发生故障时,不同装备的故障特征数据起伏不同,差异较大.传统贝叶斯网络的设备故障检测模型,多是在已知某一个或多个部件稳定状态下完成,一旦信息起伏较大,则故障决策过程会陷入反复验证的弊端,无法达到最佳的故障检测效果.提出一种基于UML建模的航空装备故障检测决策模型,对航空装备故障特征分析的基础上,采用UML对航空装备故障检测决策过程进行建模,给出了模型的需求分析,构建模型的用例图、类图以及活动图,塑造了模型的静态模型和动态模型,UML模型通过基于免疫识别神经网络模型实现航空装备故障的检测,检测模型依据免疫识别原理塑造神经网络检测器,通过训练将航空装备的故障模式信息保存在分布的检测器中,通过检测器采集被检测装备异常模式特征,当检测器同特征样本匹配时激活检测器,按照检测器的激活状态发现设备故障,完成航空装备故障的检测.实验结果说明,所提方法对航空设备故障信号检测具有较高的灵敏度和分辨率.     

电力系统投资决策动态模型的研究

一、前言作者认为,电力建设与国民经济发展,负荷增长情况构成一个互相制约、互相促进的“灰色系统”,可应用系统已有数据序列建立动态模型,确定各因素之间的定量关系.当忽略了一些次要因素之后,系统模型可表示为图1.图1中,A(ii)(i=1,2,3)反映各变量自身增长因素,a_(21),a_(31),a_(32)表示各变量互相之间的影响因素,x_1,X_2,X_3分别表示系统年工农业总产值、年平均负荷和年电力系统投资.系统各变量之间的定量关系可通过已有样本序列建立动态模型而确定.     

Decision procedures for elementary sublanguages of set theory: XI. Multilevel syllogistic extended by some elementary map constructs

This paper gives a decision procedure for the class of set-theoretic formulae in the unquantified language involving Boolean set operators, set equality and membership, domain and range operators, direct and inverse image operators, as well as the predicates SINGLEVALUED, INJECTIVE, and INV (for inverse).This paper was written while the first author was a Visiting Professor at Courant Institute, New York University, U.S.A.     

An effective architecture for Decision Support Systems

Decision Support Systems (DSS) are, by nature, general- purpose systems, because they must support a variety of managers who have different decision styles and different problems. However, it seems that no effective general-purpose DSS have yet come into existence, although the components of DSS such as data base technology, modeling techniques, inexpensive graphic display etc., have progressed to the point where we should now be able to build effective DSS.This shortcoming seems to result from the following fact: Research on decision support has focused on data enlargement and model refinement, however, little attention has been paid to DSS architecture which integrates these components of DSS. It has not been well appreciated that DSS architecture itself facilitates learning about unstructured-problem solving and enables system evolution.In this paper, we propose a DSS architecture based on the study of unstructured-problem solving and considerations of the needs of managers as non-computer specialists. We illustrate this with a system realized using this architecture.     

An Efficient Adaptive Procedure for Three-Dimensional Fragmentation Simulations

We present a simple set of data structures, and a collection of methods for constructing and updating the structures, designed to support the use of cohesive elements in simulations of fracture and fragmentation. Initially, all interior faces in the triangulation are perfectly coherent, i.e. conforming in the usual finite element sense. Cohesive elements are inserted adaptively at interior faces when the effective traction acting on those faces reaches the cohesive strength of the material. The insertion of cohesive elements changes the geometry of the boundary and, frequently, the topology of the model as well. The data structures and methods presented here are straightforward to implement, and enable the efficient tracking of complex fracture and fragmentation processes. The efficiency and versatility of the approach is demonstrated with the aid of two examples of application to dynamic fracture.     

Decision fusion systems for fault detection and identification in industrial processes

Numerous fault detection and identification methods have been developed in recent years, whereas, each method works under its own assumption, which means a method works well in one condition may not provide a satisfactory performance in another condition. In this paper, we intend to design a fusion system by combining results of various methods. To increase the diversity among different methods, the resampling strategy is introduced as a data preprocessing step. A total of six conventionally used methods are selected for building the fusion system in this paper. Decisions generated from different models are combined together through the Dempster-Shafer evidence theory. Furthermore, to improve the computational efficiency and reliability of the fusion system, a new diversity measurement index named correlation coefficient is defined for model pruning in the fusion system. Fault detection and identification performances of the decision fusion system are evaluated through the Tennessee Eastman process.     

An analysis of model-based Interval Estimation for Markov Decision Processes

Several algorithms for learning near-optimal policies in Markov Decision Processes have been analyzed and proven efficient. Empirical results have suggested that Model-based Interval Estimation (MBIE) learns efficiently in practice, effectively balancing exploration and exploitation. This paper presents a theoretical analysis of MBIE and a new variation called MBIE-EB, proving their efficiency even under worst-case conditions. The paper also introduces a new performance metric, average loss, and relates it to its less “online” cousins from the literature.     

HySAT: An efficient proof engine for bounded model checking of hybrid systems

In this paper we present HySAT, a bounded model checker for linear hybrid systems, incorporating a tight integration of a DPLL–based pseudo–Boolean SAT solver and a linear programming routine as core engine. In contrast to related tools like MathSAT, ICS, or CVC, our tool exploits the various optimizations that arise naturally in the bounded model checking context, e.g.isomorphic replication of learned conflict clauses or tailored decision strategies, and extends them to the hybrid domain. We demonstrate that those optimizations are crucial to the performance of the tool.     

An Empirical Comparison of Pruning Methods for Decision Tree Induction

This paper compares five methods for pruning decision trees, developed from sets of examples. When used with uncertain rather than deterministic data, decision-tree induction involves three main stages—creating a complete tree able to classify all the training examples, pruning this tree to give statistical reliability, and processing the pruned tree to improve understandability. This paper concerns the second stage—pruning. It presents empirical comparisons of the five methods across several domains. The results show that three methods—critical value, error complexity and reduced error—perform well, while the other two may cause problems. They also show that there is no significant interaction between the creation and pruning methods.     

模糊描述逻辑FALNUI的tableaux推理

分析了模糊描述逻辑FALNUI与模糊ER模型的关系,即模糊ER模型可以转化为FALNUI的知识库,并且模糊ER模型的可满足性、冗余性和包含关系等推理问题可以转化为FALNUI的包含推理问题,但FALNUI缺乏相应的推理算法.提出了一种基于描述逻辑tableaux的FALNUI的可满足性推理算法,证明了该推理算法的正确性,以及提出了FALNUI的Tbox扩展和去除方法,证明了FALNUI的包含推理问题可以转化为可满足性推理问题,并给出了FALNUI的包含推理算法. FALNUI的tableaux推理算法为模糊ER模型的可满足性、冗余性和包含关系等自动推理的实现提供了理论基础.     

一种基于多目标决策的指挥决策方案优选算法

指挥决策是作战指挥活动的核心,决策方案优选是指挥决策的重要阶段之一.首先,给出了多目标决策的基本概念,提出了指挥决策问题的基本假设;其次,结合多目标决策理论,根据指挥决策问题基本假设,把威胁度、目标重要性、武器防护能力等作为指挥决策方案的优选指标.提出了一种基于多目标决策理论的指挥决策方案优选算法;最后,通过仿真实例,对该算法进行了验证.得出.结合威胁度、目标重要性以及武器防护能力等指标,通过计算武器攻击效度的方法,进行方案优选是切实可行的,对提高指挥决策效率有重要的意义.