Reformulating Global Grammar Constraints

Details Reformulating Global Grammar Constraints Reformulating Global Grammar Constraints

2009-03-03

arxiv.org/abs/0903.0475v1

Computer Science

Artificial Intelligence

15 pages, 4 figures

Scientific paper

An attractive mechanism to specify global constraints in rostering and other domains is via formal languages. For instance, the Regular and Grammar constraints specify constraints in terms of the languages accepted by an automaton and a context-free grammar respectively. Taking advantage of the fixed length of the constraint, we give an algorithm to transform a context-free grammar into an automaton. We then study the use of minimization techniques to reduce the size of such automata and speed up propagation. We show that minimizing such automata after they have been unfolded and domains initially reduced can give automata that are more compact than minimizing before unfolding and reducing. Experimental results show that such transformations can improve the size of rostering problems that we can 'model and run'.

Affiliated with

Also associated with

No associations

Rating

Reformulating Global Grammar Constraints 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 Reformulating Global Grammar Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reformulating Global Grammar Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652872