Computing and Information Systems - Research Publications
Permanent URI for this collection
Search Results
1 - 10 of 12
-
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)
-
ItemTableau-based protein substructure search using quadratic programming.(Springer Science and Business Media LLC, 2009-05-19)BACKGROUND: Searching for proteins that contain similar substructures is an important task in structural biology. The exact solution of most formulations of this problem, including a recently published method based on tableaux, is too slow for practical use in scanning a large database. RESULTS: We developed an improved method for detecting substructural similarities in proteins using tableaux. Tableaux are compared efficiently by solving the quadratic program (QP) corresponding to the quadratic integer program (QIP) formulation of the extraction of maximally-similar tableaux. We compare the accuracy of the method in classifying protein folds with some existing techniques. CONCLUSION: We find that including constraints based on the separation of secondary structure elements increases the accuracy of protein structure search using maximally-similar subtableau extraction, to a level where it has comparable or superior accuracy to existing techniques. We demonstrate that our implementation is able to search a structural database in a matter of hours on a standard PC.