Stochastic Concurrent Constraint Programming

We present a stochastic version of Concurrent Constraint Programming (CCP), where we associate a rate to each basic instruction that interacts with the constraint store. We give an operational semantic that can be provided either with a discrete or a continuous model of time. The notion of observables is discussed, both for the discrete and the continuous version, and a connection between the two is given. Finally, a possible application for modeling biological networks is presented.     

约束归纳逻辑程序设计方法的研究

提出了一种新的约束归纳逻辑程序设计方法。该方法能够与自顶向下的归纳逻辑程序设计系统结合,通过在自顶向下归纳方法的一步特殊化操作中引入Fisher判别分析等方法,使得系统能够导出不受变量个数限制的多种形式的线性约束,在不需要用户诱导,不依赖约束求解器的情况下,学习出覆盖正例而排斥负例的含约束的Horn子句程序。     

Stochastic Concurrent Constraint Programming and Differential Equations

We tackle the problem of relating models of systems (mainly biological systems) based on stochastic process algebras (SPA) with models based on differential equations. We define a syntactic procedure that translates programs written in stochastic Concurrent Constraint Programming (sCCP) into a set of Ordinary Differential Equations (ODE), and also the inverse procedure translating ODE's into sCCP programs. For the class of biochemical reactions, we show that the translation is correct w.r.t. the intended rate semantics of the models. Finally, we show that the translation does not generally preserve the dynamical behavior, giving a list of open research problems in this direction.     

约束逻辑程序设计综述

一、引言 约束逻辑程序设计(Constraint Logic Program-ming．CLP)是基于人工智能(AI)中约束满足问题(Constraint Satisfaction Problem．CSP)模型的一种程序设计风范。CLP是逻辑程序设计(LP)的一种推广,是八十年代发展起来的一种新的逻辑程序设计方法。由于它继承了LP简单易懂的说明性描述方法并结合了CSP在求解问题时的效率,使它在解决很多AI问题(如组合问题、资源分配、事务安排等)时有不凡的表现。更由于AI领域中绝大多数问题可以用CLP来表示,所以这一方法已引起了人们的广泛注意,并在八十年代后期得以迅速发展。     

Constraint Programming in Structural Bioinformatics

Bioinformatics aims at applying computer science methods to the wealth of data collected in a variety of experiments in life sciences (e.g. cell and molecular biology, biochemistry, medicine, etc.) in order to help analysing such data and eliciting new knowledge from it. In addition to string processing bioinformatics is often identified with machine learning used for mining the large banks of bio-data available in electronic format, namely in a number of web servers. Nevertheless, there are opportunities of applying other computational techniques in some bioinformatics applications. In this paper, we report the application of constraint programming to address two structural bioinformatics problems, protein structure prediction and protein interaction (docking). The efficient application of constraint programming requires innovative modelling of these problems, as well as the development of advanced propagation techniques (e.g. global reasoning and propagation), which were adopted in Chemera, a system that is currently used to support biochemists in their research.     

Scenario-Based Hypersequential Programming

Hypersequential programming is a new paradigm of concurrent programming. The original concurrent program is first serialized, then the sequential version is tested and debugged, and finally the target concurrent program is synthesized by parallelizing the debugged sequential version. In hypersequential programming, testing and debugging are performed on the sequential version of the program and the correctness is preserved in the subsequent parallelization process. Therefore, it offers both higher productivity and enhanced reliability. This paper describes a practical approach to hypersequential programming using the execution history called scenario. It also formalizes the parallelization process using a new equivalence relation called scenario graph equivalence, and gives the parallelization algorithm.     

Constraint satisfaction with an object-oriented knowledge representation language

This article gives a detailed presentation of constraint satisfaction in the hybrid LAURE language. LAURE is an object-oriented language for Artificial Intelligence (AI) applications that allows the user to combine rules, constraints, and methods that cooperate on the same objects in the same program. We illustrate why this extensibility is necessary to solve some large and difficult problems by presenting a real-life application of LAURE. We describe the syntax and the various modes in which constraints may be used, as well as the tools that are proposed by LAURE to extend constraint resolution. The resolution strategy as well as some implementation details are given to explain how we obtain good performances.     

约束归纳逻辑程序设计系统

提出了一种新的约束归纳逻辑程序设计方法，并初步实现了一个自顶向下的约束归纳逻辑程序原型系统。该系统能够导出不受变量个数限制的多种形式的线性约束，得出覆盖正例而排斥负例的含约束的Hom子句程序。     

A New Approach for Weighted Constraint Satisfaction

We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and randomized local search.     

Modeling Biological Systems in Stochastic Concurrent Constraint Programming

We present an application of stochastic Concurrent Constraint Programming (sCCP) for modeling biological systems. We provide a library of sCCP processes that can be used to describe straightforwardly biological networks. In the meanwhile, we show that sCCP proves to be a general and extensible framework, allowing to describe a wide class of dynamical behaviours and kinetic laws.     

一个约束可满足性问题的演化算法求解

约束可满足性问题是一大类常出现于现实应用中的复杂问题,因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题．基于演化算法的框架进行求解。我们采用矩阵的表示方式．并设计了相应的杂交和变异算予。实验表明．演化算法能高效地解决该问题。     

On the Approximation of Stochastic Concurrent Constraint Programming by Master Equation

We explore the relation between the stochastic semantic associated to stochastic Concurrent Constrain Programming (sCCP) and its fluid-flow approximation. Writing the master equation for a sCCP model, we can show that the fluid flow equation is a first-order approximation of the true equation for the average. Moreover, we introduce a second-order correction and first-order equations for the variance and the covariance.     

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.     

Constraint Programming 2000: A Position Paper

We put forward that required enhancements to constraint programming technology include concurrency, more sophisticated control mechanisms, and new features for expressing preferences.     

约束编程与约束满足在产品装配中的应用

约束编程与约束满足问题是近三十年来在人工智能领域发展起来的一个研究方向。产品配置器近十几年来发展起来的一项技术。文中介绍约束编程及约束满足问题在按订单装配型产品配置器中的应用，并通过讨论说明了相对于传统配置方案求解过程，应用约束满足的优越性。     

约束逻辑编程中宽数据算术运算算法

提出了一种在利用约束逻辑编程生成RTL数据通路模拟矢量的方法中处理宽数据的新方法。该方法解决了现有CLP求解器所能处理的最大整数限制问题。该文设计并实现了宽数据加法、减法和乘法运算的分解算法，运算分解扩展了现有CLP的功能，使其能适应实际的数据通路设计。实验结果表明方法是有效的。     

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.     

CONSAT: A parallel constraint satisfaction system

In this paper we describe the parallelization of a medium-size symbolic fixed-point computation, CONSAT. CONSAT is a constraint satisfaction system that computes globally consistent solutions. The parallel version of CONSAT is implemented using abstractions from a parallel programming toolbox we developed. The toolbox is intended for novice parallel programmers, and programs based on abstractions from this toolbox may be executed on both uniprocessors and shared-memory multiprocessors without modifications. We explain how parallelism is introduced, and how concurrent accesses to shared data structures are handled. We will also describe the performance of CONSAT on sample inputs.     

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.