Computing and Information Systems - Research Publications
Permanent URI for this collection
Search Results
1 - 9 of 9
-
ItemDemand-Driven Normalisation for ACD Term Rewriting(Springer, 2009-09-14)ACD Term Rewriting (ACDTR) is term rewriting modulo associativity, commutativity, and a limited form of distributivity called conjunctive context. Previous work presented an implementation for ACDTR based on bottom-up eager normalisation, extended to support the conjunctive context. This paper investigates the possibility of using a demand-driven normalisation strategy for ACDTR. Again, dealing with the conjunctive context proves to be challenging. The alternative normalisation strategy is compared with the current form of eager normalisation and potential further improvements on the strategy are investigated.
-
ItemA Declarative Encoding of Telecommunications Feature Subscription in SAT(ASSOC COMPUTING MACHINERY, 2009)
-
ItemMaintaining State in Propagation Solvers(Springer, 2009-11-02)Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a propagation solver must determine how to maintain state during propagation and forward and backward search. This paper sets out the possible ways in which a propagation solver can choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. This paper also provides the first realistic comparison of trailing versus copying for state restoration.
-
ItemThe Proper Treatment of Undefinedness in Constraint Languages(Springer, 2009-11-02)Any sufficiently complex finite-domain constraint modelling language has the ability to express undefined values, for example division by zero, or array index out of bounds. This paper gives the first systematic treatment of undefinedness for finite-domain constraint languages. We present three alternative semantics for undefinedness, and for each of the semantics show how to map models that contain undefined expressions into equivalent models that do not. The resulting models can be implemented using existing constraint solving technology.
-
ItemConfidence-Based Work Stealing in Parallel Constraint Programming(SPRINGER-VERLAG BERLIN, 2009)
-
ItemLazy Clause Generation Reengineered(SPRINGER-VERLAG BERLIN, 2009-11-02)Lazy clause generation is a powerful hybrid approach to combinatorial optimization that combines features from SAT solving and finite domain (FD) propagation. In lazy clause generation finite domain propagators are considered as clause generators that create a SAT description of their behaviour for a SAT solver. The ability of the SAT solver to explain and record failure and perform conflict directed back-jumping are then applicable to FD problems. The original implementation of lazy clause generation was constructed as a cut down finite domain propagation engine inside a SAT solver. In this paper we show how to engineer a lazy clause generation solver by embedding a SAT solver inside an FD solver. The resulting solver is flexible, efficient and easy to use. We give experiments illustrating the effect of different design choices in engineering the solver.
-
ItemUsing Relaxations in Maximum Density Still Life(SPRINGER-VERLAG BERLIN, 2009)
-
ItemMinimizing the Maximum Number of Open Stacks by Customer Search(SPRINGER-VERLAG BERLIN, 2009)
-
ItemWhy Cumulative Decomposition Is Not as Bad as It Sounds(SPRINGER-VERLAG BERLIN, 2009)