逻辑程序在关系数据库完整性约束中的应用

逻辑程序设计语言具有很强的逻辑推理能力,将逻辑程序规则与数据库耦合在一起,可以扩充原有的关系数据库完整性约束规则.本文初步探讨了用逻辑程序实现关系数据库完整性约束的实现方法,该方法可以解决语义上逻辑错误的约束.     

Abstracting soft constraints: Framework, properties, examples

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster.In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier.We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.     

Constraint partitioning in penalty formulations for solving temporal planning problems

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.     

Using Constraint Programming in Selection Operators for Constraint Databases

Constraint Databases represent complex data by means of formulas described by constraints (equations, inequations or Boolean combinations of both). Commercial database management systems allow the storage and efficient retrieval of classic data, but for complex data a made-to-measure solution combined with expert systems for each type of problem are necessary. Therefore, in the same way as commercial solutions of relational databases permit storing and querying classic data, we propose an extension of the Selection Operator for complex data stored, and an extension of SQL language for the case where both classic and constraint data need to be managed. This extension shields the user from unnecessary details on how the information is stored and how the queries are evaluated, thereby enlarging the capacity of expressiveness for any commercial database management system. In order to minimize the selection time, a set of strategies have been proposed, which combine the advantages of relational algebra and constraint data representation.     

On temporal logic constraint solving for analyzing numerical data time series

Temporal logics and model-checking have proved successful in expressing biological properties of complex biochemical systems, and automatically verify their satisfaction, in both qualitative and quantitative models. In this article, we go beyond model-checking and present a constraint solving algorithm for quantifier-free first-order temporal logic formulae, with constraints over the reals. This algorithm computes the domain of the real valued variables occurring in a formula that makes it true in a model. We illustrate this approach for the automatic generation of a temporal logic specification from biological data time series. We provide a set of biologically relevant patterns of formulae, and apply them to numerical data time series of models of the cell cycle control and MAPK signal transduction. We show in these examples that this approach infers automatically semi-qualitative, semi-quantitative information about concentration thresholds, amplitude of oscillations, stability properties, checkpoints and influences between species.     

一种C程序内存访问缺陷自动化检测方法研究

符号执行是目前较为行之有效的软件缺陷自动化检测方法,计算代价昂贵与程序执行路径爆炸是两个影响其性能的关键问题.提出了一种针对C语言程序内存访问缺陷的符号执行检测方法,该方法可通过自动化构造的测试用例发现程序内部的内存访问缺陷,如缓冲区溢出、跨界访问和指针异常等.使用符号跟踪缓冲区长度的方法,一方面减少了符号变量的数量,另一方面由此精确抽象C语言库中字符串操作函数的行为,解决了符号执行过程间函数调用的步进问题;使用动态切片的方法,裁减路径探索过程中的冗余路径,从而解决在程序内部路径搜索时发生的路径爆炸问题.实验表明,提供的检测方法不但可行,而且验证代价较小,具有较强的实用性.     

Symbolic computational techniques for solving games

Games are useful in modular specification and analysis of systems where the distinction among the choices controlled by different components (for instance, the system and its environment) is made explicit. In this paper, we formulate and compare various symbolic computational techniques for deciding the existence of winning strategies. The game structure is given implicitly, and the winning condition is either a reachability game of the form p until q (for state predicates p and q) or a safety game of the form Always p.For reachability games, the first technique employs symbolic fixed-point computation using ordered binary decision diagrams (BDDs) [9]. The second technique checks for the existence of strategies that ensure winning within k steps, for a user-specified bound k, by reduction to the satisfiability of quantified boolean formulas. Finally, the bounded case can also be solved by reduction to satisfiability of ordinary boolean formulas, and we discuss two techniques, one based on encoding the strategy tree and one based on encoding a witness subgraph, for reduction to Sat. We also show how some of these techniques can be adopted to solve safety games. We compare the various approaches by evaluating them on two examples for reachability games, and on an interface synthesis example for a fragment of TinyOS [15] for safety games. We use existing tools such as Mocha [4], Mucke [7], Semprop [19], Qube [12], and Berkmin [13] and contrast the results.     

The power of ants in solving Distributed Constraint Satisfaction Problems

Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.     

Automatic software model checking via constraint logic

This paper proposes the use of constraint logic to perform model checking of imperative, infinite-state programs. We present a semantics-preserving translation from an imperative language with recursive procedures and heap-allocated mutable data structures into constraint logic. The constraint logic formulation provides a clean way to reason about the behavior and correctness of the original program. In addition, it enables the use of existing constraint logic implementations to perform bounded software model checking, using a combination of symbolic reasoning and explicit path exploration.     

基于约束的维修性设计系统研究

提出基于约束的维修性设计系统研究,在参考于约束的设计原理基础上,建立了基于约束的维修性设计系统框架,重点阐述了维修性设计中约束网络的建立,最后以维修性要求中可达性为例进行系统开发。     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.     

约束满足问题的预处理方法研究

搜索控制问题是大多数人工智能问题求解面临的一个根本间题,而约束满足是解决这一问题的常用方法之一它源于机器视觉领域中的情景标识任务,如今在人工智能的众多领域(如规划、调度、时序推理)中获得了广泛的应用,受到了人工智能界的高度重视.在近几期的UCAI和AAAI等国际人工智能会议上这方面的内容均占有一定的比重,《A币ficial In-telligence》杂志曾于1992年出了一期约束满足问题的专辑     

Spherical splines and orientation interpolation

This paper presents a method for designing spherical curves by two weighted spatial rotations. This approach is for the design of interpolating spherical curves and orientation interpolation. The same approach can be used for smoothing orientations or corners on a sphere. The designed curves have the following features: C¹ continuity, local control, and invariance under orthogonal transformations of coordinate systems.     

The effects of case libraries on problem solving

Abstract The purpose of the study was to investigate the effects of providing access to a case library of related stories while undergraduates solved ill-structured problems. While solving complex food product development problems, the experimental group accessed experts' stories of similar, previously solved problems; the comparable group accessed fact sheets (expository representation of stories' content); and the control group accessed text selected at random from a textbook dealing with issues unrelated to the stories. On multiple-choice questions assessing processes related to problem solving (prediction, inferences, explanations, etc.), experimental students out-performed the comparable and control groups. Performance on short-answer questions also assessing problem-related skills was not significantly different, in part because of test fatigue. Analysis of interviews identified a number of factors that students used in deciding how to apply their study strategies, including causal factors, grounding phenomenon, grounding in context, and outcomes.     

Models for Global Constraint Applications

In this paper we give an overview of some industrial applications built using global constraints. We look at three systems from different application domains and show the core models used to express their constraints. We also consider different search strategies that have been applied and discuss some of the application aspects.     

Vector interpolation for surface normal calculation

The problem of approximating a surface normal by linear interpolation across a surface facet is considered from a geometric point of view. This point of view makes the coordinate independence for triangular facets particularly easy to see, and provides some insight into the problem of non-uniqueness for the non-triangular case.     

Stochastic Constraint Programming: A Scenario-Based Approach

To model combinatorial decision problems involving uncertainty and probability, we introduce scenario based stochastic constraint programming. Stochastic constraint programs contain both decision variables, which we can set, and stochastic variables, which follow a discrete probability distribution. We provide a semantics for stochastic constraint programs based on scenario trees. Using this semantics, we can compile stochastic constraint programs down into conventional (non-stochastic) constraint programs. This allows us to exploit the full power of existing constraint solvers. We have implemented this framework for decision making under uncertainty in stochastic OPL, a language which is based on the OPL constraint modelling language [Van Hentenryck et al., 1999]. To illustrate the potential of this framework, we model a wide range of problems in areas as diverse as portfolio diversification, agricultural planning and production/inventory management.     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

Optimal Graph Constraint Reduction for Symbolic Layout Compaction

The compaction problem in VLSI layout can be formulated as a linear program. To reduce the execution time and memory usage in compaction, it is important to reduce the size of the linear program. Since most constraints in compaction are derived directly or indirectly from physical separation and electrical connectivity requirements which can be expressed in the form of graph constraints, we study the graph constraint reduction problem. That is the problem of producing, for a given system of graph constraints, an equivalent system with the fewest graph constraints. After observing that the problem as previously formulated is NP-hard and overrestrictive in that the maximum possible reduction is not always attainable, we propose a new formulation in which the maximum possible reduction is guaranteed. We further present a polynomial-time algorithm for the new formulation. Received September 13, 1994; revised December 4, 1995.     

基于五次hermite插值的OFDM信道估计

导频辅助信道估计方法是OFDM系统中的主要信道估计方法,可以使用LS(最小均方估计)估计导频点处的信道响应,然后通过插值算法来估计数据点的信道响应。该文提出五次hermite插值信道估计算法,目的是利用该插值算法在不同信噪比的环境下,降低误码率(BER)。通过仿真实验说明,该算法相对于传统的信道估计算法具有较良好的性能。相对于线性插值和三次样条插值,在不同的信噪比环境下具有较低的BER的优点。