Speaker: Sandeep Suresh
 
Day:  Wednesday, 11/17/2004
Room: ITE 336
Time:  3:30pm-4:05pm 

Title: Regular languages in Constraing Programming
----------------------------------------------------------------------------

Abstract: 
Global constraints are essential tools in the arsenal of any constraint Programmer. 
Their design and implementation is often complex and slows down their adoption. It is therefore
essential to have a formalism sufficiently expressive to reformulate global constraints and
synthesize pruning algorithms. 

	This talk will introduce a consistency algorithm for regular languages together 
with a method to reformulate many well known global constraints as regular languages. It will 
describe a filtering algorithm that achieves generalized arc consistency. The talk will also 
present an FSA generalization that supports a much broader class of global constraints. 

References:
-----------

1. G.Pesant. A Regular Language Membership Constraint for Finite Sequences of Variables. 
   In Proceedings of the Tenth International Conference on Principles and Practice of 
   Constraint Programming (CP 2004), volume 3258 of LNCS. Springer, 2004.

2. N. Beldiceanu, M. Carlsson, and T. Petit. Deriving Filtering Algorithms from Constraint 
   Checkers. In Proceedings of the Tenth International Conference on Principles and Practice 
   of Constraint Programming (CP 2004), volume 3258 of LNCS. Springer, 2004.   


back to CSE-TS page