Constraint Propagation and Pebble Games
From International Center for Computational Logic
Constraint Propagation and Pebble Games
Talk by Christoph Berkholz
- Location: WIL C115
- Start: 3. June 2016 at 1:15 pm
- End: 3. June 2016 at 2:15 pm
- iCal
A generic method for solving the constraint satisfaction problem is "constraint propagation" where one iteratively derives new constraints in order to shrink the search space or to detect inconsistencies in the instance. A classical and very basic algorithm in this area is the so-called k-consistency test that iteratively derives local constraints involving only k variables. In this talk I will give an introduction to this method and show that the k-consistency test is tightly connected to a simple combinatorial pebble game originally introduced in the context of finite model theory. Afterwards I will present some results on the structure and complexity of the k-consistency test that have been obtained via this pebble game in the last years.
