constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algori...
详细信息
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algorithm. In this paper, the term syntax of constraints is replaced by lambda-tree syntax, in which binding is explicit, and a new del generic quantifier is introduced, which is used to create new fresh constants.
作者：
Golden, KPang, WLNASA
Ames Res Ctr Computat Sci Div Moffett Field CA 94035 USA NASA
Ames Res Ctr QSS Grp Inc Moffett Field CA 94035 USA
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings...
详细信息
ISBN:
(纸本)3540202021
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings, and domain operations on sets of strings, can be carried out using this representation.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. this model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig9;s diet representation called the enhanced diet, which represents a fin...
详细信息
ISBN:
(纸本)3540202021
In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig's diet representation called the enhanced diet, which represents a finite domain as an AVL tree of intervals. In addition to element insertion and deletion, we show that the domain splitting used for constraints such as X less than or equal to Y can be done in O(log m) steps by adopting Crane's Algorithm, where m is the number of intervals, not the number of elements.
Multiple sequence alignment is a central problem in Bioinformatics. A known integer programming approach is to apply branch-and-cut to exponentially large graph-theoretic models. this paper describes a new integer pro...
详细信息
ISBN:
(纸本)3540202021
Multiple sequence alignment is a central problem in Bioinformatics. A known integer programming approach is to apply branch-and-cut to exponentially large graph-theoretic models. this paper describes a new integer program formulation that generates models small enough to be passed to generic solvers. the formulation is a hybrid relating the sparse alignment graph with a compact encoding of the alignment matrix via channelling constraints. Alignments obtained with a SAT-based local search algorithm are competitive withthose of state-of-the-art algorithms, though execution times are much longer.
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been deve...
详细信息
ISBN:
(纸本)3540202021
this paper presents a constraintprogramming model and search strategy to formulate and solve staff scheduling problems in health care. this is a well-studied problem for which many different approaches have been developed over the years but it remains a challenge to successfully apply any given instance of a method to the various contexts encountered. We show how the main categories of rules involved may be expressed using global constraints. We describe a modular architecture for heuristic search. the resulting flexible and rather general constraintprogramming approach is evaluated on benchmark problems from different hospitals and for different types of personnel.
We argue that the clp(X) framework is a suitable vehicle for extending logic programming (LP) with probabilistic reasoning. this paper presents such a generic framework, clp(pdf(Y)), and proposes two promising instanc...
详细信息
ISBN:
(纸本)3540202021
We argue that the clp(X) framework is a suitable vehicle for extending logic programming (LP) with probabilistic reasoning. this paper presents such a generic framework, clp(pdf(Y)), and proposes two promising instances. the first provides a seamless integration of Bayesian Networks, while the second defines distributions over variables and employs conditional constraints over predicates. the generic methodology is based on attaching probability distributions over finite domains. We illustrate computational benefits of this approach by comparing program performances with a clp(fd) program on a cryptographic problem.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
ISBN:
(纸本)3540202021
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. this model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for...
详细信息
ISBN:
(纸本)3540202021
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for highly constrained or overconstrained problems. In this paper, we present a scheme where a local search algorithm, the break-out algorithm, is used to identify hard or unsolvable subproblems and to derive a variable ordering that places the hardest subproblems first.
暂无评论