Constraint Propagation and Pebble Games
Aus International Center for Computational Logic
Constraint Propagation and Pebble Games
Vortrag von Christoph Berkholz
- Veranstaltungsort: WIL C115
- Beginn: 3. Juni 2016 um 13:15
- Ende: 3. Juni 2016 um 14:15
- 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.
