We study the global cardinality constraint (gcc) and propose an O(n1.5d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency where n is the number of variables, d the number of values in...
详细信息
Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research ...
详细信息
Many combinatorial problems can be naturally expressed as "constraint satisfaction problems". this class of problems is known to be NP-hard in general, but a number of restrictions of the general problem hav...
详细信息
constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are comm...
详细信息
constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.
Specifying and implementing a proof system from scratch requires significant effort. Logical Frameworks and Higher Order Logic programming Languages provide dedicated, high-level meta languages to facilitate this task...
详细信息
ISBN:
(纸本)9798400709692
Specifying and implementing a proof system from scratch requires significant effort. Logical Frameworks and Higher Order Logic programming Languages provide dedicated, high-level meta languages to facilitate this task in two ways: 1) variable binding and substitution are for free when meta language binders represent object logic ones;2) proof construction, and proof search, are greatly simplified by leveraging the unification procedure provided by the meta language. Notable examples of meta languages are Elf [21], Twelf [23], lambda Prolog [16], Beluga [24], Abella [8] and Isabelle [31] which have been used to implement or specify many formal systems such as First Order Logic [5], Set theory [20], Higher Order Logic [19], and the Calculus of Constructions [4]. the object logic we are interested in is Coq's type theory [28]. We aim to develop a higher-order unification-based proof search procedure using the meta language Elpi [3], a dialect of lambda Prolog. Elpi's equational theory includes beta eta-equivalence and features a higher-order unification procedure similar or equal to(m) for the pattern fragment [15]. Elpi offers an encoding of Coq terms that is suitable for meta programming [6, 9, 26, 27] but that restricts similar or equal to(m) to first-order unification problems only. We refer to this basic encoding as O. In this paper we translate unification problems in O to an alternative encoding called M, from which we derive similar or equal to(O), the higher-order unification procedure of O. similar or equal to(O) honours beta eta-equivalence for terms within the pattern fragment, and allows for the use of heuristics when the terms fall outside the pattern fragment. Moreover, as similar or equal to(O) delegates most of the work to similar or equal to(m), it can be used to efficiently simulate a logic program in O by taking advantage of unification-related optimizations of the meta language, such as clause indexing.
Temporal planning is an important problem, as in many real world planning domains actions have different durations and the goals should be achieved by a specified deadline, or as soon as possible. this paper presents ...
详细信息
Parallelization offers the opportunity to accelerate search on constraint satisfaction problems. To parallelize a sequential solver under a popular message passing protocol, the new paradigm described here combines po...
详细信息
Peer-to-peer emerges as a better way for building applications on the Internet that require high scalability and availability. Peer-to-peer systems are usually organized into structured overlay networks, which provide...
详细信息
ISBN:
(纸本)9781605585987
Peer-to-peer emerges as a better way for building applications on the Internet that require high scalability and availability. Peer-to-peer systems are usually organized into structured overlay networks, which provide key-based routing capabilities to eliminate flooding in unstructured ones. Many overlay network protocols have been proposed to organize peers into various topologies with emphasis on different networking properties. However, applications are often stuck to a specific peer-to-peer overlay network implementation, because different overlay implementations usually provide very different interfaces and messaging mechanisms. In this paper, we present a framework for constructing peer-to-peer overlay networks in Java. First, networking is abstracted by the interfaces that use URIs to uniformly address peers on different underlying or overlay networks. then, asynchronous and synchronous messaging support is built upon these interfaces. Finally, overlay networking interfaces are sketched to handle specific issues in overlay networks. We have constructed several overlay networks in this framework, and built peer-to-peer applications which are independent of overlay implementations. Copyright 2009 ACM.
Adding constraints to a basic CSP model can significantly reduce search,e.g. for Golomb rulers [6]. the generation process is usually performed by hand, although some recent work has focused on automatically generatin...
ISBN:
(纸本)3540428631
Adding constraints to a basic CSP model can significantly reduce search,e.g. for Golomb rulers [6]. the generation process is usually performed by hand, although some recent work has focused on automatically generating symmetry breaking constraints [4]and (less so)on generating implied constraints [5]. We describe an approach to generating implied,symmetry breaking and specialisation constraints and apply this technique to quasigroup construction [10].
We introduce a new approach for focusing constraint reasoning using so-called streamlining constraints. Such constraints partition the solution space to drive the search first towards a small and structured combinator...
详细信息
暂无评论