Computer Science – Artificial Intelligence
Scientific paper
2012-01-03
Computer Science
Artificial Intelligence
Submitted to CPAIOR 2012
Scientific paper
We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satis?es a Regular constraint, and each column satisfies a Gcc constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions (e.g. just 3 values, just 4 states in the automaton, or just 5 columns to the matrix). On the positive side, we identify two cases where propagation is fixed parameter tractable. In addition, we show how to improve propagation over a simple decomposition into separate Regular and Gcc constraints by identifying some necessary but insufficient conditions for a solution. We enforce these conditions with some additional weighted row automata. Experimental results demonstrate the potential of these methods on some standard benchmark problems.
Haan Ronald de
Narodytska Nina
Walsh Toby
No associations
LandOfFree
The RegularGcc Matrix Constraint does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The RegularGcc Matrix Constraint, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The RegularGcc Matrix Constraint will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-183481