**Reading**PAGE

### Peer Evaluation activity

Trusted by | 3 |

Reviews | 1 |

Downloads | 14 |

Views | 115 |

Full text requests | 1 |

Followed by | 1 |

### Total impact ?

#### Send a

### Toby has...

Trusted | 0 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

### This was brought to you by:

# A Compression Algorithm for Large Arity Extensional Constraints

## Oh la la

Your session has expired but *donâ€™t worry*, your message

has been saved.Please log in and weâ€™ll bring you back

to this page. Youâ€™ll just need to click â€œSendâ€.

**Your evaluation**is of great value to our authors and readers. Many thanks for your time.

Your **mailing list** is currently empty.

It will build up as you send messages

and links to your peers.

__No one__besides you has access to this list.

Enter the e-mail addresses of your recipients in the box below.

__Note__: Peer Evaluation will NOT store these email addresses log inYour message has been sent.

### Description

New Full text for this article was not available? Send a request to the author(s).

**Title**: A Compression Algorithm for Large Arity Extensional Constraints

**Abstract**: We present an algorithm for compressing table constraints representing allowed or disallowed tuples. This type of constraint is used for example in configuration problems, where the satisfying tuples are read from a database. The arity of these constraints may be large. A generic GAC algorithm for such a constraint requires time exponential in the arity of the constraint to maintain GAC, but Bessière and Régin showed in [1] that for the case of allowed tuples, GAC can be enforced in time proportional to the number of allowed tuples, using the algorithm GAC-Schema. We introduce a more compact representation for a set of tuples, which allows a potentially exponential reduction in the space needed to represent the satisfying tuples and exponential reduction in the time needed to enforce GAC. We show that this representation can be constructed from a decision tree that represents the original tuples and demonstrate that it does in practice produce a significantly shorter description of the constraint. We also show that this representation can be efficiently used in existing algorithms and can be used to improve GAC-Schema further. Finally, we show that this method can be used to improve the complexity of enforcing GAC on a table constraint defined in terms of forbidden tuples.

**Subject**: unspecified

**Area**: Computer Science

**Language**: English

Affiliations : |

**Url**: http://www.cse.unsw.edu.au/~tw/kwcp07-letter.ps

**Doi**: 10.1.1.138.4491

### Leave a comment

### This contribution has not been reviewed yet. review?

You may receive the Trusted member label after :

• Reviewing **10 uploads**, whatever the media type.

• Being trusted by **10 peers**.

• If you are blocked by **10 peers** the "Trust label" will be suspended from your page. We encourage you to contact the administrator to contest the suspension.

#### Please select an affiliation to sign your evaluation:

#### Please select an affiliation:

### Toby's * Peer Evaluation activity*

Trusted by | 3 |

- FLevi Lelis,
*Student, Ph.D. Level*, University of Alberta. - FMatteo Gagliolo,
*Post Doctorate*, CoMo, VUB, Brussels. - FPeer Evaluation,
*Publisher*, Peer Evaluation.

Reviews | 1 |

#### Title of the work: HP90: A general & flexible Fortran 90 hp-FE code

*8.5/10*read review - Anonymous

Downloads | 14 |

- 3The SAT Phase Transition
- 2Backbones and backdoors in satisfiability
- 2Modelling a Balanced Academic Curriculum Problem
- 1Automatically reformulating SAT-encoded CSPs
- 1On the notion of interestingness in automated mathematical discovery
- 1The Constrainedness of Search
- 1A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice
- 1The Interface between P and NP : COL , XOR , NAE , 1-in-k , and Horn SAT
- 1Estimating Search Tree Size
- 1An Empirical Study of Dynamic Variable Ordering Heuristics for the Constraint Satisfaction Problem

Views | 115 |

- 8The Interface between P and NP : COL , XOR , NAE , 1-in-k , and Horn SAT
- 4The Search for Satisfaction 1 Introduction 2 Satis ability
- 4Encodings of Non-Binary Constraint Satisfaction Problems
- 4Estimating Search Tree Size
- 3 The Complexity of Reasoning with Global Constraints
- 3Translation-based Constraint Answer Set Solving
- 3CSPlib: a benchmark library for constraints
- 2A Divergence Critic for Inductive Proof
- 2Scenario-based stochastic constraint programming
- 2Search in a Small World
- 2A Translational Approach to Constraint Answer Set Solving
- 2Manipulation of Nanson â€™ s and Baldwin â€™ s Rules
- 2Online Cake Cutting
- 2Parameterized Complexity Results in Symmetry Breaking
- 2Propagating Conjunctions of ALLDIFFERENT Constraints
- 2Reformulating Global Grammar Constraints
- 2Automatic Identification of Mathematical Concepts
- 2SAT v CSP
- 2Reformulation of Global Constraints in Answer Set Programming
- 2Decomposition of the NVALUE constraint
- 2Decompositions of Grammar Constraints
- 2Automatic Generation of Implied Clauses for SAT
- 2Backbones and Backdoors in Satisfiability
- 2The Complexity of Global Constraints
- 2Robust Solutions for Constraint Satisfaction and Optimization
- 2Super solutions in constraint programming
- 2Modelling a Balanced Academic Curriculum Problem
- 2Termination Orders for Rippling
- 1 Stochastic Constraint Programming: A Scenario-Based Approach
- 1, Fahiem Bacchus ï¿½ï¿½ï¿½ï¿½ï¿½
- 13 3 Hybrid Modelling for Robust Solving 4 4
- 1A Calculus for and Termination of Rippling
- 1A Compression Algorithm for Large Arity Extensional Constraints
- 1Finite Domain Constraint Programming Systems
- 1Filtering Algorithms for the NValue Constraint
- 1Backbones and backdoors in satisfiability
- 1Constraints, Satisfiability, and Search
- 1A theory of abstraction
- 1Circuit Complexity and Decompositions of Global Constraints
- 1The Search for Satisfaction 1 Introduction 2 Satis ability
- 1Structure and Randomness
- 1An Empirical Study of the Manipulability of Single Transferable Voting
- 1Aggregating Partially Ordered Preferences
- 1Where are the really hard manipulation problems? The phase transition in manipulating the veto rule
- 1Manipulation and gender neutrality in stable marriage procedures
- 1The Constrainedness of Search
- 1Difference Unification
- 1Symmetry within Solutions
- 1Distance Constraints in Constraint Satisfaction
- 1Global Grammar Constraints
- 1SAT v CSP
- 1Morphing: Combining Structure and Randomness
- 1Easy problems are sometimes hard
- 1A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice
- 1Modelling the Golomb Ruler Problem
- 1Automatic Concept Formation in Pure Mathematics
- 1Beyond NP : the QSAT phase transition
- 1An Empirical Study of Borda Manipulation
- 1Stable Marriage Problems with Quantitative Preferences
- 1Hybrid Modelling for Robust Solving
- 1Online Estimation of SAT Solving Runtime
- 1Cross-domain Mathematical Concept Formation
- 1The Satisfiability Constraint Gap
- 1Scaling Effects in the CSP Phase Transition
- 1Phase Transitions from Real Computational Problems
- 1The inevitability of inconsistent abstract spaces
- 1Local Consistencies in SAT
- 1Where are the hard manipulation problems?
- 1SCHOOL OF COMPUTER STUDIES Modelling the Golomb Ruler Problem 1 Introduction 2 The problem
- 1Clause Forms Generated by Bounded Model Checking
- 1A Calculus for Rippling
- 1Coloured rippling: An extension of a theorem proving heuristic

Full text requests | 1 |

#### Title of the work: Modelling the Golomb Ruler Problem

- Anonymous (1)

Followed by | 1 |

- FLevi Lelis,
*Student, Ph.D. Level*, University of Alberta.

### Toby* has...*

Trusted | 0 |

Reviewed | 0 |

Emailed | 0 |

Shared/re-used | 0 |

Discussed | 0 |

Invited | 0 |

Collected | 0 |

## Full Text request

### Your request will be sent.

Please enter your email address to be notified

when this article becomes available

**Your email**