this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, CP 2019, held in Stamford, CT, USA, France, in September/October 2019.
ISBN:
(数字)9783030300487
ISBN:
(纸本)9783030300470
this book constitutes the proceedings of the 25thinternationalconference on principles and practice of constraintprogramming, CP 2019, held in Stamford, CT, USA, France, in September/October 2019.
this book constitutes the refereed proceedings of the 10thinternational Symposium on programming Languages, Implementations, Logics, and Programs, PLILP'98, held jointly withthe 6thinternationalconference on A...
详细信息
ISBN:
(数字)9783540497660
ISBN:
(纸本)9783540650126
this book constitutes the refereed proceedings of the 10thinternational Symposium on programming Languages, Implementations, Logics, and Programs, PLILP'98, held jointly withthe 6thinternationalconference on Algebraic and Logic programming, ALP'98, in Pisa, Italy, in September 1998.;the 26 revised full papers presented were carefully reviewed and selected from a total of 68 submissions. Also included are two invited papers and abstracts of two tutorials. the papers are organized in topical sections on verification, logic programming, static analysis, software methodologies, object oriented programming, term rewriting, functional programming, metaprogramming, optimal evaluation, integration, and constraint solving.
In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either r (the constraint arity) or k (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is k + r, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT.
Shortwave radio broadcasting is the principal way for broadcasting of voice in many countries. the broadcasting quality of a radio program is determined not only by the parameters of the transmission device, but also ...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
Shortwave radio broadcasting is the principal way for broadcasting of voice in many countries. the broadcasting quality of a radio program is determined not only by the parameters of the transmission device, but also by the radio frequency. In order to optimize the overall broadcasting quality, it is desirable to designate both devices and frequencies to radio programs, subject to various constraints including the non-interference of radio programs. In this paper, we propose a two-phase approach to this constrained optimization problem. It integrates ILP and SMT solving, as well as a local search algorithm. these methods are evaluated using real data, and the results are promising.
Many combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given width. To date, none of the filt...
详细信息
ISBN:
(纸本)3540462678
Many combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given width. To date, none of the filtering algorithms proposed guaranteed domain consistency. In this paper, we present three filtering algorithms for the sequence constraint, with complementary strengths. One borrows ideas from dynamic programming;another reformulates it as a regular constraint;the last is customized. the last two algorithms establish domain consistency. Our customized algorithm does so in polynomial time, and can even be applied to a generalized sequence constraint for subsequences of variable widths. Experimental results show the practical usefulness of each.
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfactio...
详细信息
ISBN:
(纸本)9783642153952
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Omega(1) to another forbidden patterns problem Omega(2), containment of Omega(1) in Omega(2) follows. the converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Pi(p)(2)-harpd and in Sigma(p)(3).
In this paper we show how constraintprogramming (CP) techniques can improve the efficiency and applicability of grid-based algorithms for optimising surface contact between complex solids. We use BiGGER [1] (Bimolecu...
详细信息
ISBN:
(纸本)3540292381
In this paper we show how constraintprogramming (CP) techniques can improve the efficiency and applicability of grid-based algorithms for optimising surface contact between complex solids. We use BiGGER [1] (Bimolecular complex Generation with Global Evaluation and Ranking) to illustrate the method as applied to modelling protein interactions, an important effort in current bioinformatics. BiGGER prunes the search space by maintaining bounds consistency on interval constraints that model the requirement for the shapes to be in contact but not overlapping, and by using a branch and bound approach to search the models withthe best fit. this CP approach gives BiGGER some efficiency advantages over popular protein docking methods that use Fourier transforms to match protein structures. We also present an efficient algorithm to actively impose a broad range of constraints or combinations of constraints on distances between points of the two structures to dock, which allows the use of experimental data to increase the effectiveness and speed of modelling protein interactions and which cannot be done as efficiently in Fourier transform methods. this shows that constraintprogramming provides a different approach to protein docking (and fitting of shapes in general) that increases the scope of application while improving efficiency.
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values wh...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values which are neither inconsistent nor substitutable can also be deleted while conserving at least one solution. this allows us to state novel rules for the elimination of values in a binary CSP. From a practical point of view, we show that one such rule can be applied in the same asymptotic time complexity as neighbourhood substitution but is strictly stronger. An alternative to the elimination of values from domains is the elimination of variables. We give novel satisfiability-preserving variable elimination operations. In each case we show that if the instance is satisfiable, then a solution to the original instance can always be recovered in low-order polynomial time from a solution to the reduced instance.
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this pro...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this problem, sensed data must be transmitted in real-time to an operation center even in case of unavailability of traditional communication infrastructures. this implies that an ad hoc wireless communication network must be deployed, for instance using a fleet of UAVs acting as communication relays. From a technical point of view, we tackle a scheduling problem in which activities of mobile sensing robots and mobile relays must be synchronized both in time and space. Schedules produced must also be flexible and robust to the uncertainty about the duration of robot moves at execution time. the problem is modeled and solved using constraint-based local search, with some calls to graph algorithms that help defining good communication networks.
the proceedings contain 19 papers. the topics discussed include: the JavaFest: a collaborative learning technique for Java programming courses;an experimental environment for teaching Java security;patterns and tracea...
ISBN:
(纸本)9781605582238
the proceedings contain 19 papers. the topics discussed include: the JavaFest: a collaborative learning technique for Java programming courses;an experimental environment for teaching Java security;patterns and traceability in teaching software architecture;a framework for command processing in Java/Swing programs based on the MVC pattern;the PIM: an innovative robot coordination model based on Java thread migration;self-configuring object-to-relational mapping queries;portable execution of legacy binaries on the Java virtual machine;a lazy developer approach: building a JVM withthird party software;speculative improvements to verifiable bounds check elimination;constraint based optimization of stationary fields;optimized strings for Java HotSpot™ virtual machine;and SlimVM: optimistic partial program loading for connected embedded Java virtual machines.
暂无评论